一、堆(Heap)数据结构的用处

1、高效定时器

假设我们要设计一个定时器，定时器中维护了很多定时任务，每个任务都设定了一个要触发执行的时间点。定时器每过一个很小的单位时间（比如 1 秒），就扫描一遍任务，看是否有任务到达设定的执行时间。如果到达了，就拿出来执行。

像这样每次扫描的时候，把所有任务都扫描一遍，肯定很低效，如果任务比较少还好，任务比较多的话，就比较耗时。那有更高效的办法呢？答案是有的。

我们可以把每个任务都存储在优先级队列中(以触发时间为优先级的小顶堆)，这样最先执行的任务就在堆顶。每次扫描的时候只需取出堆顶任务，拿对于任务的定时时间和当前时间比较。

假设任务执行时间与当前时间的差为T。如果T<=0，就从队列中删除任务，并执行。否则定时器就可以设定在T秒之后再执行任务。从当前时间到T-1秒的时间内定时器不需要做任何事情。

Ps:假如我们需要为一个任务设定循环定时器，可以在取出堆顶任务后，将下一次任务的触发执行的时间重新加入到优先级队列。感兴趣的同学可以将上述堆的代码改造一下，将num位置的参数改造为一个对象。调整堆的时候按照对象的key作为优先级调整堆。

2、合并小文件

假设我们有 100 个小文件，每个文件的大小是 100MB，每个文件中存储的都是有序的字符串。我们希望将这些 100 个小文件合并成一个有序的大文件。

思路：名列前茅趟从这100个小文件中各取出名列前茅个字符串并加入到小顶堆中，此时堆顶元素是最小的。取出堆顶元素存入合并后的大文件。假如这个最小字符串在10.txt这个小文件中，我们就再从这个小文件取下一个字符串，加入到堆中，重新从堆中取出堆顶元素并放入合并后的大文件。依此类推，直到所有文件中的数据都放入到大文件为止。

3、较好热门关键词

有一个包含 10 亿个搜索关键词的日志文件，如何快速获取到 前二0 最热门的搜索关键词呢？

Ps:假设10亿条数据不重复的有1亿条，每个关键词占有50个字节，不重复关键词的总大小约为4.6G。如果计算机内存限定为1G，如何处理呢？

思路：将10亿个关键词按hash算法放到到10个文件中，重复的关键字会被放到同一个文件中。分别计算每个文件的前二0,然后把10个前二0 放在一起，然后取出100个关键词中，出现次数非常多的10个关键词，就是最终求得多前二0。

到这里堆的相关应用内容就介绍完了，堆是一种很好的数据结构，能解决很多实用问题，希望作者的博文能帮助您更好的学习理解堆。本文中的代码都是作者亲自实践的，可以直接拷贝下来学习参考。

延伸阅读：

二、堆是什么

堆是一种完全二叉树，复习一下完全二叉树的定义，完全二叉树的形式是指除了最后一层之外，其他所有层的结点都是满的，而最后一层的所有结点都靠左边。若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。而最小堆要求，对于任意一个父结点来说，其子结点的值都大于这个父节点,同理，最大堆就是说，其子节点的值都小于这个父节点。

上一篇

数据结构和数据库有什么关系?

下一篇

如何克服字典树(TrieTree)的缺点?