第 15 章扩展堆 — 合并与降键的摊还艺术¶

这一章讲什么: 为什么需要堆的「高级变体」——数组堆(第 14 章)合并两个堆要 O(m+n)、降键更是无从下手;而图算法(下一章的 Dijkstra/Prim) 恰恰高频需要「合并 + 降键」。本章四种结构逐级松绑: 斜堆(合并靠交换子树)→ 二项堆(森林 + 二进制进位)→ 惰性二项(先记账后清账)→ 斐波那契(降键直接割,摊还 O(1))→ 配对堆(工程上的极简终点)。 它在全书链条里的位置: 摊还分析(第 4 章伏笔)的真正主战场; 每种结构都报摊还口径而非最坏口径。

1. 顶层全景¶

  动机:数组堆 merge = O(m+n),changeKey 做不了
      │
      ├─ 斜堆:堆序二叉树,无形状约束;merge 时胜者交换左右子树再递归
      │    交换 = 摊还保险;merge/add/remove 全摊还 O(log n)
      │
      ├─ 二项堆:森林 of 二项树 BT(k)(2ᵏ 节点、高 k、根度数 k;
      │    每层节点数 = 二项系数 → 帕斯卡三角)
      │    合并 = 按度配对 + 进位(同二进制加法);O(log n) 摊还
      │
      ├─ 惰性二项堆:add 只把单节点树 push 进森林 O(1)(top 靠额外字段);
      │    remove 才一次性合并清账——「先记账,后还债」
      │
      ├─ 斐波那契堆:changeKey 不浮、直接割下整棵子树 O(1);
      │    代价:树形失控 → 妥协:丢一个孩子的节点打 marked,
      │    丢第二个孩子就连锁割;remove 时重新合并整顿
      │    摊还:add O(1)、changeKey O(1)、remove O(log n)
      │
      └─ 配对堆:merge 最简(大根把小根挂为孩子,左孩子右兄弟);
           remove:孩子堆左到右两两合并、再右到左扫一遍——「配对」之名由来

  图说:一个比一个「懒」:斜堆靠交换,二项靠进位,惰性靠欠账,斐波那契靠割,
  配对靠赌。懒的尽头是摊还表的数字。

2. 主线例子:二项堆的合并 = 二进制加法¶

二项树 BT(k):根带着 BT(0)、BT(1)、…、BT(k−1) 各一棵;恰 2ᵏ 个节点、高 k,各层节点数是帕斯卡三角的一行(二项系数,名字的由来)¹。所以 n 个元素的二项堆,森林里每棵树的存在与否,正好对应 n 的二进制位 (n=13 = 1101₂ → 有 BT(3)、BT(2)、BT(0))²。

合并两个二项堆 = 二进制加法:同度的两棵树配成对(大根吃小根、小根挂为孩子、根度数 +1),产生进位与下一度合并——就像 1+1=10。两个各 O(log n) 棵树的森林合并,O(log n) 完成³。 remove:砍掉最大根的树,把它的孩子们提升为森林成员,再合并整顿。全部操作 O(log n) 摊还⁴。

惰性版把「加法」再懒一步:add 不做任何合并,新树直接入林 O(1), top 靠一个额外维护的 top 字段;直到 remove 才把整片森林合并清账—— 一连串便宜的 add 摊掉偶尔一次贵的 remove⁵。

3. 核心原理¶

3.1 斜堆:一行交换的摊还保险¶

斜堆是堆序二叉树,没有任何结构约束(可以长得很歪),全部操作都建立在一个递归 merge 上:

  merge(H1, H2):根大者胜;胜者交换左右子树,
  然后把(交换后的)右子树与对方递归 merge

交换是全部的秘密:不交换的朴素合并会攒出恶性循环的歪树 (习题 15.2 给了两个具体的坏序列);每次合并顺手把树「拧」一下, 可证摊还 O(log n)⁶。add = 造单节点堆 + merge;remove = 删根 + merge(左, 右)——全章最短的堆实现。注释里交代:斜堆与左倾堆同源, 「更省空间、实现更容易」,左倾堆本书不讲。

3.2 斐波那契堆:降键的 O(1) 摊还革命¶

图算法反复调用 decreaseKey(Dijkstra 松弛边时、Prim 更新连接代价时), 把降键从 O(log n) 压到 O(1) 摊还,是斐波那契堆(Fredman & Tarjan)的全部动机 (论文标题直说「用于改进网络优化算法」)⁷。

机制三件套:

降键 = 割:键变优时不浮、直接把该节点连同子树从父节点摘下, 作为新树入林——摘除必须是 O(1),所以兄弟链表升级为循环双向 (单链表摘节点要 O(log n) 找前驱,破坏目标)⁸。
marked 妥协:放任割会让树形失控。规矩:非根节点只许丢一个孩子 (丢时打 marked);丢第二个孩子时,自己也被割——可能连锁向上割。这是「形状」与「速度」的停战线⁹。
remove 时整顿:同惰性版,删最大根、孩子升林、全体合并。摊还账:add O(1)、changeKey O(1)、remove O(log n); 「斐波那契」之名来自摊还分析中某个量满足斐波那契递推(书中未展开)。

3.3 配对堆:把合并做到最简,把复杂度押给删除¶

配对堆(Tarjan 后来推荐的「更简单结构」)回到了多叉: 根 + 有序子堆列表(左孩子右兄弟表示,第 13 章的工具直接复用)。 merge 简单到不能再简单:大根把小根挂为最新一个孩子, 两行解构赋值完事¹⁰。

代价转移给 remove:删掉根后得到一排子堆,两趟合并—— 左到右两两配对合并(A+B, C+D, E+F…,名字由来), 再把合并结果从右到左逐个 meld 成一棵树。摊还分析复杂(书中不展开),实测极快,是工程实现的热门选择¹¹。

3.4 摊还口径的统一¶

全章性能表都用星号标摊还值。逻辑链条在第 4 章就埋好: 惰性结构「先记账后还债」,一串操作的总成本被平均—— 偶尔一次 O(n) 的整顿(remove)被一串 O(1) 的 add 摊薄⁵。这也是本书第一次让读者看到:摊还不是分析技巧,是设计手法。

4. 作者的判断与证据¶

动机链 explicit:每节开头都先报「上一结构在哪个操作上还不够好」 (斜堆←数组堆 merge 慢;惰性←二项 add 的 O(log n);斐波那契←惰性降键还贵; 配对←斐波那契太复杂)——结构进化由性能缺口驱动,不靠情怀⁷。
摊还数字全部给表,且星号约定(摊还 vs 保证)统一声明; 证明照例略去,「数学从略」多次明说。
诚实交代理论-工程落差:配对堆「摊还分析复杂,但实测优秀, Tarjan 本人推荐」;斐波那契堆理论最优但常数大、实现繁¹¹。
结构间亲缘用注释织网:左倾堆、binomial 系数、二进制加法、循环链表(第 10 章)——每处借用都点明出处。

判断(我们的,不是书里的): 本章是全书「渐进松绑」叙事的顶点: 形状约束(第 12 章 AVL 严守)→ 结构约束(第 14 章完全树)→ 无约束+交换保险(斜堆)→ 无约束+记账(惰性)→ 无约束+割+标记(斐波那契)。每松一次绑,都换一种记账方式买单——约束不会消失,只会转移成摊还账本上的条目。 如果错,会错在: 「约束转移成账本」是我们的比喻; 且斐波那契堆在实践中常被配对堆/简单堆击败(常数与缓存),理论最优 ≠ 工程最优—— 书里暗示了但没给数据(补充,不在书里,来自通用知识)。

5. 边界与局限¶

摊还证明全部缺席:斜堆的交换论证、斐波那契堆的势函数分析, 只给结论;要严谨得去原始论文或算法分析教材。
pairing heap 的 changeKey 本章未实现(习题 15.4 指路), 摊还界至今没有像斐波那契那样干净的理论刻画(补充,不在书里,来自通用知识)。
没有 benchmark:所有「更快」都是渐进口径 + 经验断言,无实测数据。
JS 的数组/对象开销让这些指针结构的真实常数比 C 实现难看—— 书中未讨论(补充,不在书里)。

6. 可带走的¶

数组堆两短板:merge O(m+n)、降键做不了;高级堆全在补这两门课。
斜堆:merge 时胜者交换左右子树;交换 = 摊还保险;全操作摊还 O(log n)。
二项树 BT(k):2ᵏ 节点、层节点数=二项系数;堆 = 森林,合并 = 二进制进位加法。
惰性二项:add O(1) 只挂树(top 靠字段),remove 才合并清账——记账式摊还。
斐波那契:降键 = O(1) 割 subtree(兄弟须循环双向链表);marked 限制连锁割; 摊还 add O(1)/降键 O(1)/remove O(log n)——图算法的理论加速器。
配对堆:merge 两行(大根吃小根);remove 两趟成对合并;实测快、实现最简。
选型:要 merge 选斜/二项/配对;要降键摊还最优选斐波那契; 要代码最短选配对或斜堆。

7. 原文地图¶

主题	原书章	原文位置
斜堆与左倾堆注	Skew Heaps	`text/46-fm-skew-heaps.txt:12`(搜「leftist heap」)
斜堆合并交换	Skew Heaps	`text/46-fm-skew-heaps.txt:63`(搜「swaps its children」) · `text/46-fm-skew-heaps.txt:82`(搜「amortized」)
二项树性质	Binomial Heaps	`text/47-fm-binomial-heaps.txt:12`(搜「order k」) · `text/47-fm-binomial-heaps.txt:31`(搜「binomial coefficients」)
惰性二项的记账哲学	Lazy Binomial Heaps	`text/48-fm-lazy-binomial-heaps.txt:4`(搜「O(1)」) · `text/48-fm-lazy-binomial-heaps.txt:91`(搜「balance」)
斐波那契动机与割	Fibonacci Heaps	`text/49-fm-fibonacci-heaps.txt:4`(搜「decreaseKey」) · `text/49-fm-fibonacci-heaps.txt:18`(搜「more than one child」)
循环双向链表的理由	Fibonacci Heaps	`text/49-fm-fibonacci-heaps.txt:26`(搜「doubly linked」)
配对堆合并与两趟	Pairing Heaps	`text/50-fm-pairing-heaps.txt:4`(搜「orchard」) · `text/50-fm-pairing-heaps.txt:101`(搜「in pairs」)

出处:「Binomial Heaps」第 12–31 段(text/47-fm-binomial-heaps.txt:12,搜「order k」)。原文:BT(k) 的根带着孩子 BT(0)…BT(k−1);「BT(k) 恰有 2ᵏ 节点、高 k」;各层节点数为二项系数(帕斯卡三角)见第 31 段。 ↩
出处:「Binomial Heaps」第 20 段(text/47-fm-binomial-heaps.txt:20,搜「2k」)。原文:「BT(k) 恰有 2ᵏ 节点」;森林 ↔ 二进制位的对应是 BT 尺寸的直接推论(13=8+4+1)。 ↩
出处:「Binomial Heaps」合并一节(text/47-fm-binomial-heaps.txt:39,搜「two trees」)。原文:同度两树配对,大根吃小根、根度数+1,进位与下一度合并;「与二进制加法同构」的直观贯穿全节。 ↩
出处:「Binomial Heaps」性能说明(text/47-fm-binomial-heaps.txt:4,搜「forest of heaps」)。原文(惰性节转述):全操作摊还 O(log n);add 的摊还 O(1)。 ↩
出处:「Lazy Binomial Heaps」第 4–7、91 段(text/48-fm-lazy-binomial-heaps.txt:4,搜「O(1)」;:91,搜「balance」)。原文:add 不合并只 push、top 字段维护;「许多快操作与一次慢操作的平衡,换来好的摊还成本」。 ↩↩
出处:「Skew Heaps」第 63–97 段(text/46-fm-skew-heaps.txt:63,搜「swaps its children」;:82,搜「amortized」)。原文:胜者交换子树再递归 merge;「交换带来好的摊还性能;不交换更差(习题 15.2)」;摊还 O(log n) 见第 145 段。 ↩
出处:「Fibonacci Heaps」第 4、12 段(text/49-fm-fibonacci-heaps.txt:4,搜「decreaseKey」)。原文:图算法频繁 decreaseKey,「比 O(log n) 更快的降键很重要」;Fredman 与 Tarjan 的论文标题《Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms》。 ↩↩
出处:「Fibonacci Heaps」第 15–26 段(text/49-fm-fibonacci-heaps.txt:26,搜「doubly linked」)。原文:降键直接割下子树入林 O(1);「单链表摘除要 O(log n) 找前驱,破坏目标」——所以兄弟链表升级为循环双向。 ↩
出处:「Fibonacci Heaps」第 18 段(text/49-fm-fibonacci-heaps.txt:18,搜「more than one child」)。原文:非根节点不许丢超过一个孩子;每次丢孩子打 marked;丢第二个时自己被割,可能连锁。 ↩
出处:「Pairing Heaps」第 61–73 段(text/50-fm-pairing-heaps.txt:61,搜「merge = (heap1, heap2)」)。原文:大根把小根挂为新的第一个孩子;两行解构赋值完成。 ↩
出处:「Pairing Heaps」第 101–117 段(text/50-fm-pairing-heaps.txt:101,搜「in pairs」)。原文:remove 删根后子堆「左到右两两合并,再右到左合并」;「pairing heaps 之名即来自成对合并」;与斐波那契的对比见第 12 段注(Tarjan 推荐的更简单结构)。 ↩↩

第 15 章 扩展堆 — 合并与降键的摊还艺术¶