算法与数据结构 / 优先队列与堆家族 待审核 6 页

优先队列与堆家族

优先队列只有一份契约：不论入队顺序，每次取走优先级最高的那个。实现它的结构统称堆，彼此的差别不在这份契约上，而在「哪几个操作被做快了」。

本系列分三条线。数组式堆把完全树压进一个数组，没有指针、访存连续——二叉堆是起点，d 叉堆调的是分支数（树更矮，但每层要多比几次），索引堆补上 decrease-key，那是 Dijkstra 与 Prim 拿到教科书复杂度的前提。指针式可并堆换一个主操作：把两个堆合成一个应该是 $O(\log n)$ 而不是 $O(n)$ ，leftist 与 skew 用两种方式约束右脊，pairing heap 则把结构简化到只剩「一次比较、挂过去」。工程形态关心的是另一批问题：堆节点能不能内嵌进业务对象、任意删除怎么做、以及定时器这类场景为什么常常不用堆。

每页都能改输入、单步推进，并把各结构在同一批 key 上的比较次数与移动次数摆在一起比。

数组式堆：完全树压进一个数组

把完全二叉树按层序编号存进数组，父子关系变成下标算术，于是既没有指针开销、访存又连续。这条线上的三页依次是二叉堆的两个基本动作、分支数 $d$ 的取舍，以及为 decrease-key 补上的位置索引。

priority-queue · binary heap

优先队列与二叉堆

从朴素实现的代价出发，单步演示二叉堆的 sift-up / sift-down、 $O(n)$ heapify 与两版堆排序，再看它作为内部零件出现在哪些经典算法里。

d-ary heap · 树高 · cache line

d 叉堆：分支数怎么选

把二叉堆的分支数从 2 改成 d，树高降到 log_d n。push 变便宜，pop 变贵——每下降一层要多比 d−1 次。比较次数在 d=3 取最小，移动次数一路降到 d=32，两个最优点不在一处。

pos 数组 · decrease-key · 惰性删除

索引堆与 decrease-key

二叉堆答不出「某个元素现在在哪一格」，于是做不了 decrease-key。索引堆用一份 pos 数组补上这半份映射，Dijkstra 的教科书复杂度由此成立。工程上更常见的替代是惰性删除。

两个不同的最优点

d

叉堆的

d

取多少最好，取决于要最小化哪个量，而两个量的最优点不在一处。 比较次数：每下降一层要做

d

次比较（

d-1

次挑出最小的孩子，1 次与父亲比），层数是

\log_d n

，于是总比较正比于

d / \ln d

，在

d = e

处取极小——整数里就是 3。4000 个 key 的实测把这条曲线画得很准：pop 的比较次数

d = 2

时 75931，

d = 3

时 74918（最低），

d = 4

回到 81226。 移动次数：它只与树高有关，一路单调下降——同一批 key 从

d = 2

的 92991 次降到

d = 32

的 27589 次。现实中的实现（如 Dijkstra 的 4 叉堆变体）选 4 或 8 而不是 3，理由不在这两张表上：

d

个孩子在数组里连续排列，

d = 8

、每个 key 8 字节时恰好一条 cache line 装满，一次访存把全部候选带回。这是访存账，不是比较账。

数组式堆 · 延伸阅读

d-ary heap — Wikipedia en.wikipedia.org $d$ 叉堆的下标算术、各操作的复杂度，以及它在 Dijkstra 上把复杂度改善为 $O(E \log_{E/V} V)$ 的分析。
Priority Queues (Algorithms, 4th ed. §2.4) algs4.cs.princeton.edu Sedgewick 的索引优先队列 IndexMinPQ：pos 数组的维护与它在 Dijkstra、Prim 里的用法。
Dijkstra's algorithm — Wikipedia en.wikipedia.org 各种优先队列下的复杂度表：二叉堆 $O(E \log V)$ 、Fibonacci heap $O(E + V \log V)$ ，以及惰性删除写法的分析。

可并堆：把 meld 当作主操作

数组式堆合并两个堆只能重建，代价 $O(n)$ 。若 meld 是高频操作，就得换成指针结构：leftist heap 用 null path length 约束右脊长度，skew heap 干脆不存这个量、靠无条件交换换取摊还界，pairing heap 把结构简化到极致而实测最快。

null path length · 右脊 · meld

可并堆：leftist 与 skew

数组式堆合并两个堆只能重建，代价与总元素数同阶。指针结构把 meld 降到 O(log n)：leftist heap 用 null path length 约束右脊长度，skew heap 不存这个字段、靠无条件交换孩子换取摊还界。

两趟合并 · cascading cut · 摊还界

pairing heap 与 Fibonacci heap

pairing heap 只剩「一次比较、挂过去」一个结构操作，代价全压在 delete-min 的两趟合并上。Fibonacci heap 的 O(1) 摊还 decrease-key 实测常输给二叉堆。

pairing heap 的两趟合并不能省

delete-min 摘掉根之后要把它的一堆孩子并成一个。看似「从左到右依次并进一个累加器」最简单，实测这个写法会把代价推高两个数量级：3000 个 key 全部弹出，两趟合并做 52713 次比较，单趟从左到右做 2241413 次——差 42 倍，且差距随

n

继续张开。原因是单趟会让累加器一路变成一条长链：每次 merge(acc, kid) 都把其中一个挂到另一个下面，累加器的度数线性增长，下一次 delete-min 就要面对一个有

n

个孩子的根。两趟里的第一趟先把孩子两两配对，度数当场减半，这一步才是摊还界的来源。两种写法给出的输出序列完全一样——退化的是代价，不是结果。这类 bug 不会被正确性测试抓到，只有把比较次数记下来才看得见。

可并堆 · 延伸阅读

Sleator & Tarjan · Self-Adjusting Heaps (1986) cs.cmu.edu skew heap 的出处：去掉 npl 字段、无条件交换孩子，用摊还分析换回同阶的界。
Fredman, Sedgewick, Sleator & Tarjan · The Pairing Heap (1986) cs.cmu.edu pairing heap 的原始论文，含两趟合并的定义与「为何单趟不行」的讨论。
Fredman & Tarjan · Fibonacci Heaps (1987) dl.acm.org Fibonacci heap 与它给 Dijkstra、Prim 带来的 $O(E + V \log V)$ ，摊还分析的经典范例。
Moret & Shapiro · An empirical assessment of algorithms for constructing a MST dl.acm.org 实测层面的对照：理论更优的堆在真实数据上常常输给二叉堆，常数与访存是主因。

工程形态：堆在真实系统里长什么样

教科书的堆存的是 key，真实系统的堆存的是「指向业务对象的引用」，且常常要支持任意删除、要嵌进已有的内存布局、要和 GC 或分配器打交道。这一组看这些约束如何改变实现，以及定时器这类场景为什么常常绕开堆。

intrusive heap · 任意删除 · 墓碑

堆在真实系统里的形态

教科书的堆存 key，真实系统的堆存业务对象。libuv 把节点内嵌进对象、自己不分配内存；Go 的定时器堆没有位置字段，取消只能打墓碑。定时器负载常常干脆绕开堆。

工程形态 · 延伸阅读

本站 · 时间轮 Timing Wheel @vega/playground 定时器管理的另一条路：环形数组加槽位，添加与删除都是 $O(1)$ 。本系列在工程形态一页与它对照。
libuv · heap-inl.h github.com 侵入式二叉堆的工业实现：节点结构内嵌在业务对象里，堆本身不分配任何内存。
Go runtime · time.go github.com Go 的定时器堆：曾是每个 P 一个 4 叉堆，后改为最小堆加惰性删除，注释里记着改动的理由。