07｜堆：如何实现一个高效的优先队列？
黄清昊
该思维导图由 AI 生成，仅供参考
你好，我是微扰君。
上一讲学习了基于红黑树的 ordered_map 的实现，今天我们来介绍另外一种有趣的树，heap，也就是堆。堆的应用非常广泛，我们常说的堆排序的堆就是指这种树状数据结构，除此之外还可以用来解决诸如 TopK，或者合并多个有序小文件之类的问题。
堆也是我们最后一个基础数据结构容器 - 优先队列的常见底层实现方式。
优先队列
你一定还记得之前讲过的线性数据结构 queue 吧，也就是队列，一种先进先出的数据结构，生活中这种先进先出的场景也很常见，我们当时举了一个在餐厅排队取号的例子，先来的人一定会先取到号，也先被叫到号，这完美地符合队列的语义。
那如果我们现在希望允许一部分人插队呢？比如在医院中，大部分病人都有序的挂号排队，但这时候如果来了一个重症病患，我们就很可能需要破坏先进先出的规则，让医生优先诊断治疗这位病患。这种场景中的队列，我们就可以定义为“优先队列”。
优先队列中的每个元素，我们会赋予它一个优先级，优先级相同的元素我们还是遵循先进先出的原则，但一定会保证队列中优先级更高的元素先出队，即使它进队时间更晚。比如例子中的重症病患来的并不早，但依旧得到了医生的优先治疗。
对于这种优先队列，我们应该如何高效地实现呢？
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文深入介绍了基于堆实现高效优先队列的技术细节。首先，文章强调了基于堆的实现方式相对于基于线性表的方式更为高效，详细介绍了二叉堆的设计原理和优势，以及堆元素在内存中的存储方式。其次，通过对插入和删除操作的分析，读者可以了解堆的操作过程和代码实现。文章还强调了堆的特性和实现方式相对于其他数据结构的简单性和高效性。此外，文章还介绍了优先队列的扩容机制和相关的实现细节。总的来说，本文内容深入浅出，适合读者快速了解堆和优先队列的实现原理及其在实际应用中的优势。文章还提出了开放问题，引发读者思考和讨论。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《业务开发算法 50 讲》，新⼈⾸单¥59
《业务开发算法 50 讲》，新⼈⾸单¥59
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(7)
- 最新
- 精选
- Paul Shan堆排序并不是稳定排序，所以相同序号没法做到先进后出，如果要保证先进先出，一种方法是再加一层，每个节点用一个队列而不是简单的节点表示，这样所有权值相同的节点就进入了一个队列，然后用这个队列保证先进先出。还有一种方法是修改对键值的定义，也就是把时间因素考虑近来，让时间作为排序的次要因子，这样就可以保证键值唯一。
作者回复: 正解
2021-12-25517 
丶昊哥，能不能讲解一下每篇文章后问题的答案呀？感觉自己心里有了答案，但是没有一个参考，总感觉不大对作者回复: 好的好的 不过一般都会有同学回复的还不错的 我回头看看是不是可以置顶之类的～
2021-12-282
muyinliu这也说明 PQ 默认情况下实现的是小顶堆。 --- 是否可以考虑把图都换成小顶堆的图，我第一次看本章的时候很疑惑，总觉得图和代码对不上号作者回复: 好的 我之后修改一下～
2022-03-21
ZeroIce上面那个满二叉树是不是和完全二叉树混淆？2022-02-0713
余先声要保证相同优先级的元素也需要保证FIFO的特性，那么可以新引入一个自增id的概念。比较器当判断优先级相等的时候，就按id的大小进行排序，id小的在前，大的在后2022-05-151
蒋某人尚需顿悟java堆内存和这个堆结构有什么联系吗2023-04-19归属地：上海2
SevenHe一点收获，在遇到满二叉树或稠密二叉树的场景时，可以考虑用数组来存放，有如下优势： 1. 空间利用率高，比起指针的方式，也更满足内存局部性原理 2. 无需后继节点指针，内存占用也更小 3. 寻址效率高，结合位运算即可快速寻址2022-03-22
收起评论
