两趟合并 · cascading cut · 摊还界

pairing heap 与 Fibonacci heap

前一页的两种可并堆各自维护一棵二叉树，形状受右脊约束。这一页的两种堆放弃了形状约束：节点可以有任意多个孩子，结构在操作过程中随意生长，靠摊还分析把总代价兜回来。

放弃形状约束换到的东西很具体。pairing heap 的实现短到几十行，实测速度长期领先其他可并堆；Fibonacci heap 把 decrease-key 压到 $O(1)$ 摊还，Dijkstra 的复杂度随之降到 $O(E + V \log V)$ ，这是至今仍写在教科书里的最优界。

1 · 唯一的结构操作

pairing heap 的节点持有一个 key 与一串孩子，没有度数上限、没有 mark 位、没有 npl。整套结构只有一个动作：

$\mathrm{merge}(a, b) = \begin{cases} a \text{（把 } b \text{ 追加进 } a \text{ 的孩子列表）} & a.\mathrm{key} \le b.\mathrm{key} \\ b \text{（把 } a \text{ 追加进 } b \text{ 的孩子列表）} & \text{否则} \end{cases}$

一次比较，一次挂接。其余操作都由它拼出来：insert 是与单节点堆 merge，meld 就是 merge 本身，decrease-key 是把节点连同子树从父亲那里剪下来再与根 merge。三者都是 $O(1)$ 。

代价全部推给了 delete-min。摘掉根之后剩下一串孩子，必须把它们并回一棵树，而这串孩子可能有成百上千个。

2 · 两趟合并

原论文规定的做法分两趟：第一趟从左到右把孩子两两配对各做一次 merge，第二趟把配对结果从右到左累积成一棵树。

看上去更简单的写法是省掉第一趟，直接从左到右一路并进一个累加器。这个版本正确，代价却是另一个量级。

图 2-1 · 两种 delete-min 写法在同一批 key 上的比较次数（柱高按对数刻度）与逐项对照。可换 key 个数，观察倍率如何随规模张开。

3000 个 key 全部弹出，两趟做 52713 次比较，单趟做 2241413 次，相差 42.5 倍。倍率随规模张开：300 个 key 时是 7.5 倍，1000 个时是 18.0 倍。两种写法吐出的序列逐项相同。

机制可以直接量出来。单趟的每一次 merge(acc, kid) 都把其中一棵挂到另一棵下面，累加器的度数线性增长，下一次 delete-min 面对的就是一个孩子上千的根。记录每次 delete-min 时根的孩子数并取平均：两趟是 18.6，单趟是 748.1，比值 40.3——与比较次数的比值 42.5 几乎重合。

注 · 峰值不是判据。两种写法的根度数峰值相差不大（3000 个 key 时是 2022 与 2964），差 46%；真正差 40 倍的是平均值。摊还界约束的本来就是总和，单次的尖峰它一句话也没说。本页起初拿峰值作对照指标，画出来两根柱子几乎一样高，换成平均值才看出差距。

这类退化不会被正确性测试抓到。输出完全正确，只有把比较次数记下来才看得见。

3 · cut 与 mark 位

Fibonacci heap 用另一条路做到同样的 $O(1)$ insert 与 meld：根表是一个环形双向链表，插入只是往环里挂，完全不做整理。整理推迟到 delete-min，那时按度数把根表里的树两两 link，度数相同的合并，直到每个度数至多一棵。

真正的创新在 decrease-key。改小 key 之后若破坏了与父亲的堆序，就把这个节点连同子树整棵 cut 下来丢进根表， $O(1)$ 。为防止树被剪得太散，每个节点带一个 mark 位：失去第一个孩子时打标记，失去第二个孩子时自己也被切走，并向上递归。这条规则保证度数为 $d$ 的节点其子树至少含 $F_{d+2}$ 个节点， $F$ 是 Fibonacci 数列，结构由此得名，也由此把最大度数压在 $O(\log n)$ 。

图 3-1 · 同一张图上索引二叉堆与 Fibonacci heap 跑 Dijkstra 的操作计数。表格列出比较、写入、link 与 cut，下方两栏是比较次数与写入次数的柱状对照。可换顶点数与边密度。

$V = 800$ 、 $E = 3199$ 的随机图上，两者的操作序列完全一样：都是 800 次入堆、539 次 decrease-key。Fibonacci heap 的 key 比较次数是 8884，索引二叉堆是 12999，前者只有后者的 0.68 倍。指针写入的账反过来：69768 对 13722，前者是后者的 5.08 倍。

注 · decrease-key 多数时候什么都没做。把那 539 次调用按实际动作拆开：365 次改完 key 之后仍不小于父亲的 key，直接返回；14 次的节点本来就在根表里，没有父亲可剪；只有 160 次真的剪了一刀，其中 4 次触发了 cascading cut，合计 164 次 cut。 $O(1)$ 摊还这个界在这批数据上远未被用满，真正花掉的是 consolidate 那 4265 次 link。

实测常输给二叉堆的原因就摆在这两栏里。省掉的那个对数因子落在比较上，而比较在整数 key 上几乎免费；多出来的开销落在指针上，每个节点四根指针加一个 mark 位、分散在堆内存里，每一次 link 与 cut 都是随机访存。Larkin、Sen 与 Tarjan 在 2014 年的系统实验里给出同一个结论：在几乎所有真实负载上，简单结构赢。

4 · 摊还界与最坏界

图 4-1 · 六种堆五个操作的复杂度对照，最后一栏区分最坏界与摊还界。可选一个操作高亮该列，或只看给最坏界的结构。

这张表横着读没有意义，因为没有哪一种堆在所有列上占优。有意义的读法是先定住负载里最贵的那个操作，再看那一列。

最后一栏才是选型时最容易被忽略的一项。leftist heap 的 $O(\log n)$ 对每一次操作都成立；skew、pairing、Fibonacci 三种给的都是摊还界，单次操作可以任意贵，只保证 $m$ 次的总和。渲染循环与撮合引擎有单帧延迟预算，它们要的是第一类。

pairing heap 的 decrease-key 那一格写作 $o(\log n)$ ，小写的 $o$ 表示严格低于对数级而紧界至今未定。Fredman 在 1999 年证明它不可能做到 $O(1)$ ：任何满足 pairing heap 那套操作定义的实现，decrease-key 的摊还代价有 $\Omega(\log \log n)$ 的下界。这条结论把 pairing heap 与 Fibonacci heap 在渐近意义上永久分开，而实测里赢的仍然是前者。

5 · 参考文献

Fredman, M. L., Sedgewick, R., Sleator, D. D., & Tarjan, R. E. (1986). The pairing heap: A new form of self-adjusting heap. Algorithmica, 1(1), 111–129.
Fredman, M. L., & Tarjan, R. E. (1987). Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3), 596–615.
Fredman, M. L. (1999). On the efficiency of pairing heaps and related data structures. Journal of the ACM, 46(4), 473–501.
Larkin, D. H., Sen, S., & Tarjan, R. E. (2014). A back-to-basics empirical study of priority queues. In Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX), 61–72.