1. 堆的应用一：优先级队列
优先级队列，顾名思义，它首先应该是一个队列。队列最大的特性就是先进先出，而在优先级队列中，数据的出队顺序则是按照优先级来，优先级高的先出队。
实现优先级队列的方法有很多，但是用堆来实现是最直接、最高效的。堆和优先级队列非常相似，一个堆就可以看作一个优先级队列。从优先级队列中取出优先级最高的元素，就相当于取出堆顶元素。
1.1. 合并有序小文件
假设我们有 100 个小文件，每个文件的大小是 100 MB，每个文件中存储的都是有序的字符串，现在我们要将这些小文件合并成一个有序的大文件，就要用到优先级队列。
整体思路有点像归并排序的合并操作。我们从这 100 个文件中各自取出第一个字符串放入到数组中，然后比较大小，将最小的字符串放入合并后的文件，并从数组中删除。
假如这个最小的字符串来自文件 1.txt，那么我们就再从这个文件中取出下一个字符串放入数组，重新进行比较，找出最小的字符串加入到大文件中，然后从数组中删除。以此类推，直到我们遍历完所有小文件为止。
这里，我们每次从数组中找出最小的字符串都要进行一遍遍历。显然，这不是很高效。
其实，我们就可以把数组改成优先级队列，或者说是堆。我们把从小文件中取出来的字符串放入到小顶堆，那么，堆顶的元素就是最小的也就是优先级最高的元素。每次，我们都将堆顶元素放入到大文件中并将其从堆顶删除，然后再取出下一个字符串放入堆中，直到所有小文件都遍历完毕即可。
删除堆顶元素和往堆中插入数据的时间复杂度都为 ，
代表堆中的数据个数，这里就是 100，比数组快多了。
1.2. 高性能定时器
假设我们有一个定时器，定时器中维护了很多定时任务，每个任务都设定了一个 要触发执行的时间点。定时器每隔一个很小的时间单位（比如 1 秒）就会扫描一遍任务，看是否有任务需要执行。
但是，这样做就非常低效。首先，如果距离任务执行时间点还太远，那么许多的扫描都是徒劳的。其次，每次我们都需要扫描整个任务列表，如果任务列表很大的话，就会比较耗时。
针对此，我们就可以按照任务执行时间的先后顺序来建立一个优先级队列，优先级最高的任务就是小顶堆的堆顶元素。
我们拿堆顶元素的执行时间点，与当前时间点相减，得到一个时间间隔 T。也就是说，从当前时间点再等待 T 时间，才有第一个任务需要执行。在这期间，我们就无需再查询了。等到 T 时间后，我们取出堆顶任务执行，然后再重新计算差值，继续等待。
2. 堆的应用二：利用堆求 Top K
求 Top K 的问题可以分为两类。一类是静态数据，数据集合事先知道，不会再变。另一类是动态数据，数据集合事先并不知道，有数据动态地加入到数据集合中。
针对静态数据，我们可以维护一个大小为 K 的小顶堆。顺序遍历数组，如果数据小于堆顶元素，则不作处理继续遍历；如果数据大于堆顶元素，则删除堆顶元素并将当前数据插入到堆中。遍历完数组后，堆中数据即为前 K 大元素。
遍历数据需要 的时间复杂度，而每一次堆操作需要
的时间复杂度，所以最坏情况下，
个元素都入堆，时间复杂度为
。
针对动态数据，我们可以一直维护一个大小为 K 的小顶堆，每当有新数据加入到集合中时，我们就拿它和堆顶元素进行比较，然后按照和上面静态数据一样的策略更新堆。这样，无论任何时候需要查询前 K 大数的时候，我们都可以直接返回队中的元素即可。
3. 堆的应用三：利用堆求中位数
所谓中位数，就是处于中间位置的数字。如果数据的个数为奇数，那么第 个数据就是中位数；如果数据的个数为偶数，那么于中间位置的数字有两个，我们可以取第
或第
个数据作为中位数。
对于静态数据，我们可以先对数据进行排序，然后取出中间位置的数据即可。虽然排序的代价比较大，但是边际成本会很小，我们只需要排序一次。
但是，针对动态数据，如果每次查询中位数的时候都对数据进行排序，那效率就不高了。借助堆这种数据结构，我们不用排序，就可以非常高效地找到中位数。
我们需要维护两个堆，一个大顶堆，一个小顶堆。大顶堆中存储前半部分数据，小顶堆中存储后半部分数据，而且小顶堆中的数据都大于大顶堆中的数据。这时候，大顶堆的堆顶元素也就是我们要找的中位数。
如果是偶数情况，那么大顶堆就有 个数据，小顶堆就有
个数据；如果是奇数情况，那么大顶堆就有
个数据，小顶堆就有
个数据。
如果新加入的数据小于等于大顶堆的堆顶元素，我们就将这个数据插入到大顶堆；否则，我们就将这个数据插入到小顶堆。
这时候，就有可能会出现两个堆中的数据个数不符合前面的约定。我们可以从一个堆中不停地将堆顶元素移动到另一个堆中，来让两个堆中的数据个数重新满足上面的约定。
除此之外，我们还可以利用同样的原理来快速求出其他百分位的数据。假如我们要找出接口的 99% 响应时间？
所谓 99% 的响应时间，就是对响应时间排完序后处于 99%n 位置的数据。我们依然建立一个大顶堆和一个小顶堆，其中大顶堆中保存 99%n 的数据，而小顶堆中保存 1%*n 的数据，然后依然按照上面处理中位数的操作对两个堆进行维护。
获取更多精彩，请关注「seniusen」!
网友评论