29 | 堆的应用：如何快速获取到Top 10最热门的搜索关键词？
王争
该思维导图由 AI 生成，仅供参考
搜索引擎的热门搜索排行榜功能你用过吗？你知道这个功能是如何实现的吗？实际上，它的实现并不复杂。搜索引擎每天会接收大量的用户搜索请求，它会把这些用户输入的搜索关键词记录下来，然后再离线地统计分析，得到最热门的 Top 10 搜索关键词。
那请你思考下，假设现在我们有一个包含 10 亿个搜索关键词的日志文件，如何能快速获取到热门榜 Top 10 的搜索关键词呢？
这个问题就可以用堆来解决，这也是堆这种数据结构一个非常典型的应用。上一节我们讲了堆和堆排序的一些理论知识，今天我们就来讲一讲，堆这种数据结构几个非常重要的应用：优先级队列、求 Top K 和求中位数。
堆的应用一：优先级队列
首先，我们来看第一个应用场景：优先级队列。
优先级队列，顾名思义，它首先应该是一个队列。我们前面讲过，队列最大的特性就是先进先出。不过，在优先级队列中，数据的出队顺序不是先进先出，而是按照优先级来，优先级最高的，最先出队。
如何实现一个优先级队列呢？方法有很多，但是用堆来实现是最直接、最高效的。这是因为，堆和优先级队列非常相似。一个堆就可以看作一个优先级队列。很多时候，它们只是概念上的区分而已。往优先级队列中插入一个元素，就相当于往堆中插入一个元素；从优先级队列中取出优先级最高的元素，就相当于取出堆顶元素。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
堆是一种重要的数据结构，在本文中介绍了堆的几个重要应用场景。首先，堆可以用于实现优先级队列，对于处理优先级较高的数据具有很大帮助。其次，堆可以高效地解决求Top K和中位数等问题，无论是对于静态数据集合还是动态数据集合。文章通过具体的例子生动地展示了堆的实际应用，如合并有序小文件和高性能定时器。此外，文章还介绍了利用哈希算法对大数据进行分片处理的方法，以解决内存限制的问题。总之，本文通过实际例子和详细解释，使读者能够快速了解堆的应用和实现方法，为解决实际问题提供了重要的帮助。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《数据结构与算法之美》，新⼈⾸单¥68
《数据结构与算法之美》，新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(240)
- 最新
- 精选
oatlmy老师，请问为什么评价算法性能是根据时间和空间复杂度，而不是别的参数？是因为计算机结构是冯诺依曼体系，除了输入输出设备和控制器，就剩下运算器和存储器了吗？作者回复: 你理解的没错
2018-11-282125
Miletos“如果新加入的数据小于等于大顶堆的堆顶元素，我们就将这个新数据插入到大顶堆；如果新加入的数据大于等于小顶堆的堆顶元素，我们就将这个新数据插入到小顶堆。” 1. 这里不太对劲，前文中说到，小顶堆的堆顶大于大顶堆的堆顶。 如果新进元素在小顶堆堆顶和大顶堆堆顶元素值之间，没有规定插入哪个堆。 我觉得，是不是只要判断一次就可以了。新进元素值大于等于小顶堆堆顶元素的，插入小顶堆，否则插入大顶堆。 当某一个堆数据过多时再重新移动堆顶元素。 2. 求中位数的源数据中，是否允许重复数据？作者回复: 1 你说的对 我改下 多谢指正 2 可以重复
2018-11-284105
豪华老师，分片求取前十是不是有bug，如果有一个关键词在每一组分片中都是前第十一位，在整个十亿中个数总和是第一位，是不是用分片求出了错误的结果呢？作者回复: 不会的 相同的关键词经过哈希之后只会到一台机器
2018-11-28634
AaaaaaaaaaayoutopK 是不是应该先要填满堆，后面插入的时候再做删除操作作者回复: 是的。
2019-02-20231
geraltlaush之前遇到qq的一个面试题，一个用户的登录了qq，如果五分钟内用户没有检测到心跳包，就需要用户重新登录，登录后重新计时五分钟，是不是也用高等计时器来管理海量用户的计时登录问题，把qq号和时间五分钟当成堆节点，有心跳来就调整堆，把五分钟规定时间剩下最少的用户放在堆顶，后台线程每次扫描的时候取堆顶元素，然后计算剩余的等待时间，等规定时间到了，就取堆顶元素，判断是否为0，如果为0，就需要重新登录，一直取堆顶，直到取到不为0的元素，然后计算剩余等待时间，线程休眠，等到了规定时间再来，老师你看这个方案可行不作者回复: 赞，可行。
2019-07-261028
ZX看了这一章，发现堆删除任意元素这个方法毫无意义啊。只有删除堆顶元素才有意义作者回复: 是的啊 没有说过删除任意元素呢
2018-12-02425
蚂蚁内推+v数据是动态的，为什么不能用数组呢？我们维护一个size为k的有序数组（用快排，复杂度是klogk，插入法建堆也是klogk），然后每来一个元素，就把数组的第一个元素比较，如果大就插入，如果小就舍弃。插入使用二分，也是logn。没感觉堆有什么好处啊？老师作者回复: 维护数组有序的话，你用二分是可以查找的元素要插入的位置，但真正插入这个元素到这个位置的时候，你得搬移数据腾空间啊，这个复杂度就是O(n)了。 建堆虽然耗时，那只需要建一次堆，之后插入数据，只需要logk的时间复杂度的
2019-08-28619
小花小黑的铲屎官我们遍历这 10 亿个关键词，并且通过某个哈希算法对其求哈希值，然后哈希值同 10 取模，得到的结果就是这个搜索关键词应该被分到的文件编号。 这样并不能保证每个文件都是一亿条数据吧？可能多也可能少吧？作者回复: 是的 你说的没错
2018-12-1414
Allen高性能定时器，使用堆数据结构不一定是最优解，“环形队列”也许更好一点作者回复: 👍 各有利弊吧
2018-12-1811
攻城拔寨如果我要1%到99%响应时间，这样建的堆就有点多了作者回复: 这需求...具体问题具体分析吧
2018-12-0911
收起评论
