堆与优先队列

想象一家急诊室：病人按紧迫程度（而不是到达时间）接受治疗。最危重的病人总是最先被处理，哪怕他是最后到达的。这就是优先队列的行为模型——一种"根据优先级出队"而非"先进先出"的数据结构。

朴素地维护这样一个队列，每次取出"最紧迫的"都要扫一遍全部元素：一百万个元素里找最值要比较一百万次。堆（Heap）把这件事压到 $\log_2 10^6 \approx 20$ 次比较——这就是它存在的理由。

堆由 J.W.J. 威廉姆斯（J. W. J. Williams）在 1964 年提出，发表在《ACM 通讯》上，标题是《算法 232：堆排序》（Algorithm 232 – Heapsort）。换句话说，堆最初是作为一种排序算法的副产品诞生的，随后才成为优先队列的标准实现。它是一种奇妙的数据结构：用数组实现了一棵树，同时保证了极高的缓存友好性。

核心概念：堆序性#

二叉堆（Binary Heap）是一棵满足以下两个条件的完全二叉树：

1. 完全性：所有层都填满，最后一层从左到右填入
2. 堆序性（Heap Property）：
3. - 最大堆（Max-Heap）：每个节点的值 $\geq$ 其所有子节点的值
4. - 最小堆（Min-Heap）：每个节点的值 $\leq$ 其所有子节点的值

关键洞察：完全二叉树可以用数组表示，不需要指针！

若根节点存在下标 $1$（1-indexed），则： - 节点 $i$ 的父节点：$\lfloor i/2 \rfloor$ - 节点 $i$ 的左子节点：$2i$ - 节点 $i$ 的右子节点：$2i + 1$

这种数组表示不仅节省指针的内存开销，更重要的是缓存友好——相关节点在内存中是连续的，CPU 缓存命中率高。

基本操作#

插入（Insert）：将新元素放到末尾，然后"上浮（sift-up / bubble-up）"：与父节点比较，若违反堆序则交换，重复直到满足。时间 $O(\log n)$。

取最值（Extract-Max / Extract-Min）：取根节点（最大/最小值），将末尾元素移到根，然后"下沉（sift-down / heapify-down）"：与最大/最小的子节点比较并交换，重复直到满足。时间 $O(\log n)$。

查看最值（Peek）：直接返回根节点，$O(1)$。

建堆（Heapify / Build-Heap）：将任意数组建成堆。朴素方法逐个插入 $O(n \log n)$。Floyd 建堆算法：从最后一个非叶节点开始，逐个向前对每个节点执行 sift-down，时间 $O(n)$。

走一遍：7 元素建堆与一次 extract-min#

取数组 $A = [7, 3, 9, 1, 8, 5, 4]$（下标从 1 开始），建最小堆。它对应的初始树是：

            7(1)
         /        \
      3(2)        9(3)
     /    \      /    \
   1(4)  8(5)  5(6)  4(7)
```

Floyd 建堆从最后一个非叶节点 $i = \lfloor 7/2 \rfloor = 3$ 开始，逐个向前：

一共 4 次交换。校验堆序：$A[1]=1 \le 3, 4$；$A[2]=3 \le A[4]=7, A[5]=8$；$A[3]=4 \le A[6]=5, A[7]=9$。全部满足。

注意第 3、4 行：下标 1 上的元素 7 连续下沉了两层才停。这就是 sift-down 与 sift-up 的形状差异——一个节点可能要走到底，也可能第一步就停。

现在做一次 extract-min：

返回 1，2 次交换、4 次比较（每层一次"哪个孩子小"加一次"要不要换"）。新的堆顶是 3，是剩下六个数里最小的。校验：$3 \le 7, 4$；$7 \le 9, 8$；$4 \le 5$。成立。

这里最该注意的是第 1 步那个看起来很粗暴的操作——把最后一个元素搬到根。为什么不是"把较小的孩子提上来"？因为堆必须保持完全二叉树：数组不能有洞。用末尾元素填坑是唯一能一步维持完全性的做法，代价是引入一个通常很大的值，需要重新下沉。这个"先破坏再修复"的套路是堆的所有操作的共同骨架。

逐个插入 vs Floyd 建堆：一个 7 元素的对照#

上面 4 次交换看着不多，换成"逐个插入"呢？同样的 7 个数按原序插入，需要 5 次交换——差 1 次，几乎看不出差别。$n = 7$ 太小，渐近差异还没展开。

换成对逐个插入最不利的输入：$[7, 6, 5, 4, 3, 2, 1]$（对最小堆来说，每个新元素都是当前最小值，必须一路上浮到根）。

同样的输入，2.5 倍差距。$n$ 越大差距越开：$n = 10^6$ 时逐个插入的上界是 $n\log_2 n \approx 2\times10^7$ 步，Floyd 是 $\approx 10^6$ 步——20 倍。下一节把这个 $O(n)$ 算出来。

自底向上建堆为什么是 $O(n)$#

直觉容易搞反：每个节点最多下沉 $\log n$ 层，$n$ 个节点不该是 $n\log n$ 吗？

关键在代价的分布极不均匀。完全二叉树里，一半的节点是叶子（下沉代价 0），四分之一在高度 1（最多沉 1 层），八分之一在高度 2……代价大的节点恰好是数量少的那些。

高度为 $h$ 的节点最多 $\lceil n/2^{h+1}\rceil$ 个，每个下沉最多 $h$ 步，于是总步数

$$\sum_{h=0}^{\lfloor \log_2 n\rfloor} \frac{n}{2^{h+1}}\cdot h \;=\; \frac{n}{2}\sum_{h=0}^{\infty}\frac{h}{2^{h}}$$

用等比级数的标准恒等式 $\sum_{h\ge0} h x^{h} = \dfrac{x}{(1-x)^2}$，代入 $x = 1/2$ 得 $\dfrac{1/2}{(1/2)^2} = 2$。所以总步数 $\le \dfrac{n}{2}\times 2 = n$。

上界不是"$O(n)$ 的某个常数倍"，就是 $n$ 本身。 把 $n = 10^6$ 的各层摊开看，收敛得非常快：

这张表最该注意的是峰值在 $h = 1$ 和 $h = 2$，各占 25 万步；此后每层的贡献都在掉。真正能沉满 20 层的只有根那一个节点，贡献 20 步——占总量的两百万分之一。

该记住的是这个思维方式：当代价分布随规模指数衰减时，"最坏情况乘以个数"这种估法会大幅高估。反过来，extract-min 每次都从根开始，走的正好是最长的那条路，所以它没有这种便宜可占——同样的树，$O(n)$ 建堆和 $O(\log n)$ 取最值，差别全在起点是叶子还是根。

堆排序#

堆排序（Heapsort）由 J.W.J. Williams 在 1964 年提出：先 $O(n)$ 建堆，然后 $n$ 次取出最大值，每次取出后维护堆——总计 $O(n \log n)$，且原地进行（$O(1)$ 额外空间）。

与快速排序相比，堆排序最坏情况同样 $O(n \log n)$（无退化风险），但实践中因访问模式跳跃、缓存命中率差，通常比快速排序慢若干倍。

于是它在工业界落到了一个很特别的位置：不是主力，而是保险丝。 C++ 标准库的 std::sort 主流实现是 introsort（Musser，1997）——以快速排序为主体，一旦递归深度超过 $2\lfloor\log_2 n\rfloor$ 就切换成堆排序跑完剩下的部分。这个设计把两者的优点各取一半：正常输入走快排的好常数，被精心构造的退化输入（能让快排掉到 $O(n^2)$ 的那种）撞上深度限制后由堆排序接手，保证最坏 $O(n\log n)$。

堆排序在现代代码里最重要的用途，是让快速排序变得可以放心使用。 一个算法可以因为"最坏情况有保证"而有价值，即使它的平均性能从来不是最好的。

优先队列的应用场景#

优先队列是众多算法的核心子结构：

Dijkstra 最短路径：每次从优先队列中提取当前距离最小的未访问节点。用二叉堆：$O((V + E) \log V)$；用斐波那契堆（理论上）：$O(E + V \log V)$。

Prim 最小生成树：每次从优先队列取代价最小的跨越边。

A* 搜索：按估计总代价 $f = g + h$ 的优先队列驱动搜索。

Top-K 问题：从 $n$ 个元素中找最大的 $k$ 个。用最小堆维护大小为 $k$ 的窗口，时间 $O(n \log k)$。

任务调度：操作系统调度器按优先级管理就绪队列。

中位数维护：用一个最大堆和一个最小堆分别维护前半段和后半段，可在 $O(\log n)$ 内动态维护流数据的中位数。

堆的变种#

d-叉堆（d-ary Heap）#

每个节点有 $d$ 个子节点（而非 2 个）。Insert 变快（上浮高度 $O(\log_d n)$），Extract-Min 的每层要比较 $d$ 个子节点，单层变贵。

把 $n = 10^6$ 的账算清楚，会发现真正的收益不在比较次数上：

下沉的比较次数完全一样（都是 40）——$d$ 变大让每层更贵、层数更少，两者恰好抵消。所以如果只数比较次数，四叉堆看不出任何好处。

好处在最后一行。每下降一层就是一次跳到数组里另一个位置的访问，很可能是一次缓存缺失；层数减半，缓存缺失就减半。更妙的是四个孩子在数组里连续存放：4 个 8 字节的元素是 32 字节，能塞进一条 64 字节的缓存行——挑出最小的那个孩子只需要一次内存访问。

这不是纸上推演。LaMarca 与 Ladner 在 1996 年《实验算法学刊》创刊卷的论文《The Influence of Caches on the Performance of Heaps》里测过：对较大的队列，四叉堆的缓存失效次数约为二叉堆的一半。这是"缓存感知算法设计"这个方向最早的经典结果之一。

再加上插入的比较次数直接减半，就解释了 Dijkstra 这类场景（插入/降键远多于取最值）为什么偏爱 $d = 4$。该记住的是：$d$ 的选择不是复杂度问题，是缓存行宽度除以元素大小的问题。 元素越小、缓存行越宽，最优的 $d$ 就越大。

二项堆（Binomial Heap）#

由 Jean Vuillemin 在 1978 年提出。支持高效的合并（Merge）操作：$O(\log n)$ 时间合并两个堆。而二叉堆的合并需要 $O(n)$。

二项堆由多棵"二项树"组成，结构类似二进制计数。

斐波那契堆（Fibonacci Heap）#

由 Michael Fredman 和 Robert Tarjan 在 1984/1987 年提出。支持摊销 $O(1)$ 的 Insert 和 Decrease-Key（降低某元素的优先级），$O(\log n)$ 的 Extract-Min。

这使得 Dijkstra 算法理论复杂度降至 $O(E + V \log V)$（用二叉堆是 $O((V+E)\log V)$）——在稠密图上是显著的改进。

然而，斐波那契堆的常数因子大，实现复杂，实践中常常不如简单的二叉堆或 d-叉堆快——这是理论与工程之间著名的"差距"。

差距具体差在哪里，可以从内存布局看出来。二叉堆的一个元素在数组里就是一个 8 字节的数，位置由下标算出；斐波那契堆的一个节点要带父指针、子指针、左右兄弟指针（4 个指针 = 64 位机上 32 字节），再加度数和标记位，一个节点五六十字节。同样存 $10^6$ 个元素，二叉堆约 8 MB 连续内存，斐波那契堆是几十 MB 的散落节点。 前者顺着数组走，后者每一步都是指针追逐。

$O(1)$ 摊还的 Decrease-Key 是斐波那契堆的核心卖点，但它的实现方式恰恰是最伤缓存的那种：把节点从父亲的孩子链表里摘下来，接到根链表上，可能触发级联切断（cascading cut）——一连串的指针改写，每一次都可能是一次缓存缺失。渐近上省下的那个 $\log n$，被兑换成了几十次内存往返。

Larkin、Sen 与 Tarjan 在 ALENEX 2014 的《A Back-to-Basics Empirical Study of Priority Queues》里把十种堆放在一起实测——隐式 d-叉堆、配对堆、斐波那契堆、二项堆、显式 d-叉堆、rank-pairing 堆、quake 堆、violation 堆、rank-relaxed weak 堆、严格斐波那契堆。两个结论值得记住：最优选择强烈依赖输入，不存在一个通吃的赢家；而斐波那契堆因为每节点内存大、操作常数高，被配对堆全面压制，在 Decrease-Key 上尤其明显。论文还报告了 L1 缓存失效率与实际运行时间的强相关——又一次指向同一个结论。

有意思的是斐波那契堆并没有因此变得没用：它证明了 $O(1)$ 摊还 Decrease-Key 在理论上可达，这个存在性结论本身重塑了此后三十年优先队列研究的目标。一个赢不了基准测试的数据结构仍然可以改变一个领域——它划定了可能性的边界。

实际基准（现代硬件）：

配对堆（Pairing Heap）#

Michael Fredman、Robert Sedgewick、Daniel Sleator 和 Robert Tarjan 在 1986 年提出。实现简单，实践性能接近斐波那契堆，是目前许多场景下的首选。

现场：调度器用红黑树，定时器用堆#

"按优先级出队"的系统里，堆并不总是赢家。两个真实的例子恰好落在分界线的两边。

Linux 进程调度器：不用堆#

Linux 从 2.6.23 起的 CFS（Completely Fair Scheduler）把所有可运行任务放进一棵红黑树，键是 p->se.vruntime（该任务已消耗的虚拟运行时间），每次挑树里最左的那个任务来跑，并另外维护 rq->cfs.min_vruntime。2023 年 10 月的 Linux 6.6 用 Peter Zijlstra 实现的 EEVDF（Earliest Eligible Virtual Deadline First）算法替换了 CFS 的调度策略。

一个只需要"取最小"的场景，为什么用平衡树而不是堆？关键在于调度器需要的操作不止取最小：

1. 任意删除。 任务会阻塞、会退出、会被迁移到别的 CPU——随时要从队列里拿掉一个不在堆顶的元素。堆能做，但你必须知道它在数组里的下标；而堆的每次上浮/下沉都会搬动元素，于是每个任务都得维护一个"我现在在数组第几格"的回指，且每次交换都要更新两处。红黑树里节点的地址永不改变，任务结构里直接嵌一个 rb_node，删除时把这个节点地址交给树就行。
2. 不只要最小值。 EEVDF 要找的是"有资格运行的任务中虚拟截止时间最早的那个"——这是一个带条件的查询，需要在树上做搜索式下降；堆的部分有序性支持不了这种查询。

该记住的是这条判别式：如果你只需要反复取最值、元素身份不重要，用堆；如果元素需要稳定的身份、需要被任意删除或按其他条件搜索，用平衡树。 堆用"下标由结构算出"换来了零指针开销，代价正是失去了稳定的元素身份。

事件循环的定时器：正是堆#

反过来，Node.js 底层的 libuv 用的就是一个最小堆（源码 src/heap-inl.h，src/timer.c）。定时器天生适合堆：只需要"下一个该触发的是谁"，而定时器一旦触发就从堆顶弹出，不需要任意删除（取消定时器相对罕见）。

一个细节很有意思：libuv 的比较函数 timer_less_than 先比 timeout，超时时刻相同时再比 start_id ——一个从 loop->timer_counter 取的单调递增序号。为什么需要这个次级键？因为堆不是稳定的：两个 setTimeout(fn, 0) 在堆里的相对顺序取决于交换过程，而 JavaScript 的语义要求它们按注册顺序回调。用一个递增计数器当次级键，是给不稳定的数据结构补上稳定性最便宜的办法。

Dijkstra 的 decrease-key：多数实现根本不做#

教科书里的 Dijkstra 用 decrease-key：发现更短路径时，把队列里那个节点的键降下来。但要在堆上做这件事，就要维护"节点 → 数组下标"的映射，并在每次交换时更新它——回到了上面调度器的那个麻烦。

于是绝大多数实际实现改用惰性重复插入：发现更短距离时，直接把 (新距离, 节点) 再压一次；弹出时如果发现这个距离已经过期（大于已确定的距离）就丢掉。Python 的 heapq 模块只提供 heappush / heappop / heapreplace，没有 decrease-key，所以标准的 Python Dijkstra 只能这么写。

代价是堆里最多有 $O(E)$ 个条目而不是 $O(V)$ 个。以一张 $V = 2\times10^7$、$E = 5\times10^7$ 的路网为例：$\log_2(5\times10^7) \approx 25.6$，$\log_2(2\times10^7) \approx 24.3$——每次操作贵约 5%，换掉了整套下标维护代码和它带来的 bug。

这就是为什么斐波那契堆在 Dijkstra 上的理论优势兑现不了：它的 $O(1)$ Decrease-Key 优化的，恰好是那个大家已经用 5% 的代价绕开了的操作。

堆的视角：部分有序#

堆是一种部分有序（Partially Ordered）数据结构——它不保证完整的排序，只保证"最值可以 $O(1)$ 访问，下一最值可以 $O(\log n)$ 提取"。这种"不完全排序"正是它比全排序高效的原因。

相比之下，若想要 $O(1)$ 查询任意元素，需要哈希表；若想要有序遍历，需要平衡 BST。堆在"只需反复取最值"这一场景下是最优的工具。

跨域连接#

• 级数：自底向上建堆是线性时间，因为代价分布极不均匀——一半节点是叶子无需下沉，高度为 $h$ 的节点数按 $2^h$ 递减而代价只线性增长。求和用的是 $\sum h/2^h$ 那条等比级数恒等式，结果恰好是二。由此得到一个通用的思维方式：代价随规模指数衰减时，"最坏情况乘以个数"会严重高估。
• 操作系统：进程调度器需要的操作不止取最小——任务会阻塞、退出、被迁移，随时要删掉一个不在顶端的元素，而每次调整都会搬动元素，元素的"身份"因此不稳定。所以调度器用平衡树而非堆。判别式可以直接拿来用：只反复取最值、身份不重要就用堆；需要任意删除或按其他条件搜索就用平衡树。
• 气体动理论：事件驱动的分子动力学用优先队列存"下一次碰撞的时刻"，每次碰撞后涉及粒子的所有旧事件全部作废。这本该是任意删除，实现上却普遍改用惰性失效——不删，弹出时发现过期就丢掉。这与最短路实现里放弃降键、直接重复入队是同一条工程判断：维护"元素在数组第几格"的映射，代价通常高于多存几个废条目。
• 订单簿：限价单簿看起来正是两个优先队列，买方取最高价、卖方取最低价。但撤单极其频繁且必须按订单号定位，撮合引擎因此普遍用按价格分桶的链表而非堆——桶内维持时间优先，撤单是常数时间的链表摘除。同一个"按优先级出队"的需求，删除模式一变，数据结构就跟着换。
• 器官分配伦理：等待名单的优先级随病情恶化而变，候选人也会退出或被移植走，两种操作都要求按身份定位。这正是堆最不擅长的场景，但更关键的是这里对可解释性的要求：排序规则必须能被逐条复核与申诉，因而不能藏在数据结构的调整过程里。算法选择在这里受制于问责，而不只是复杂度。

参考文献#

• Williams, J. W. J. "Algorithm 232: Heapsort." Communications of the ACM 7(6), 347–348 (1964).
• Floyd, R. W. "Algorithm 245: Treesort." Communications of the ACM 7(12), 701 (1964). （自底向上线性建堆）
• Fredman, M. L. & Tarjan, R. E. "Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms." Journal of the ACM 34(3), 596–615 (1987).
• LaMarca, A. & Ladner, R. "The Influence of Caches on the Performance of Heaps." ACM Journal of Experimental Algorithmics 1 (1996). DOI 10.1145/235141.235145. （四叉堆的缓存失效实测）
• Larkin, D. H., Sen, S. & Tarjan, R. E. "A Back-to-Basics Empirical Study of Priority Queues." ALENEX, 2014. （十种堆的实测对比）
• Musser, D. R. "Introspective Sorting and Selection Algorithms." Software: Practice and Experience 27(8), 983–993 (1997). （introsort 与 $2\lfloor\log_2 n\rfloor$ 深度限制）
• Fredman, M., Sedgewick, R., Sleator, D. & Tarjan, R. "The Pairing Heap: A New Form of Self-Adjusting Heap." Algorithmica 1(1), 111–129 (1986).
• Brodal, G. S., Lagogiannis, G. & Tarjan, R. E. "Strict Fibonacci Heaps." STOC, 2012.
• Cormen, T. et al. Introduction to Algorithms (CLRS). 4th ed. MIT Press, 2022. （第6章 Heapsort，第19章 Fibonacci Heaps）
• Linux 内核文档 CFS Scheduler 与 EEVDF Scheduler（p->se.vruntime 键、最左节点、6.6 版的算法替换）。
• libuv 源码 src/heap-inl.h 与 src/timer.c（最小堆实现与 start_id 次级排序键）。

延伸阅读#

• Sedgewick, R. & Wayne, K. Algorithms. 4th ed. Addison-Wesley, 2011. （第2.4章优先队列与堆排序）
• Vuillemin, J. "A Data Structure for Manipulating Priority Queues." Communications of the ACM 21(4), 309–315 (1978). （二项堆原始论文）
• Python 标准库文档 heapq — https://docs.python.org/3/library/heapq.html（只有 push/pop、没有 decrease-key 的最小实现）