堆和优先队列
优先队列是一种抽象数据类型，它总是产生优先级最高（或最低）的元素；堆是标准的基于树的结构，通过高效的插入和提取最小元素操作来实现优先队列。
用 PaperMind 寻找选题即将推出Find papers & topics
Tools & resources
Learn & explore
视频即将推出
Definition
优先队列是一种抽象数据类型，支持插入带优先级的元素和提取优先级最高的元素；堆是一种基于树的数据结构，满足堆属性——每个节点的键值相对于其子节点都保持一致的顺序——从而高效地实现优先队列。
Scope
本主题涵盖优先队列抽象数据类型（ADT）及其堆实现：二叉堆及其数组表示、堆属性和上浮/下沉操作、堆排序，以及先进的可合并堆，如二项堆和斐波那契堆，它们改进了键值减小和合并操作的成本。它与图算法（Dijkstra、Prim）和事件驱动模拟相关联，这些算法都依赖于优先队列。
Core questions
- 定义优先队列ADT的操作有哪些，堆如何实现它们？
- 堆属性如何允许在常数时间内查找最小值，并在对数时间内进行插入/提取操作？
- 二叉堆如何在数组中紧凑存储，以及如何在线性时间内构建？
- 堆排序如何利用堆在O(n log n)时间内进行原地排序？
- 当需要频繁减小键值时，斐波那契堆等可合并堆何时能改进算法？
Key concepts
- 优先队列ADT
- 堆属性
- 二叉堆
- 基于数组的堆表示
- 上浮和下沉
- 线性时间构建堆
- 堆排序
- 斐波那契堆和二项堆
Key theories
- 堆属性和数组表示
- 二叉堆是一种近似完全二叉树，其中每个节点的键值都优于其子节点的键值；它可以存储在数组中，通过隐式父子索引，实现O(log n)的插入和提取操作，以及O(1)的查找最小值操作。
- 斐波那契堆的摊还效率
- 斐波那契堆支持O(1)摊还时间的键值减小操作和O(log n)摊还时间的提取最小值操作，从而改进了Dijkstra和Prim等执行大量键值减小操作的算法的渐近运行时间。
Clinical relevance
优先队列是重要的基础设施：它们在操作系统调度程序中对就绪任务进行排序，在离散事件模拟中管理事件，驱动最佳优先搜索和A*搜索，并在Dijkstra和Prim算法中提供边界。堆排序提供了一种原地O(n log n)排序，并保证了最坏情况下的性能界限。
History
J. W. J. Williams于1964年引入了二叉堆和堆排序，Robert Floyd不久后提出了线性时间构建堆的过程。二项堆（Vuillemin，1978）和斐波那契堆（Fredman和Tarjan，1987）增加了高效的合并和摊还的键值减小操作，从而提高了经典图算法的运行时间。
Key figures
- J. W. J. Williams
- Robert W. Floyd
- Michael Fredman
- Robert Tarjan
Related topics
Seminal works
- williams1964
- fredman1987
- cormen2009
Frequently asked questions
- 为什么将二叉堆存储在数组中而不是使用指针？
- 二叉堆是一种近似完全二叉树，因此其节点可以清晰地映射到连续的数组索引上：索引i处的节点其子节点位于2i和2i+1。这避免了指针开销，改善了缓存性能，并使导航成为简单的算术运算。
- 斐波那契堆何时值得其复杂性？
- 斐波那契堆提供了O(1)摊还时间的键值减小操作，这改进了像Dijkstra最短路径算法在稠密图上的渐近运行时间。实际上，它们较大的常数因子意味着更简单的二叉堆通常更快，因此它们主要在理论界限和特殊情况下才显得重要。