第 19 章 斐波那契堆 (Fibonacci Heaps)
核心结论
-
合并堆 (Mergeable Heap)：MAKE-HEAP/INSERT/MINIMUM/UNION/EXTRACT-MIN/DECREASE-KEY/DELETE 七操作；斐波那契堆 INSERT、UNION、DECREASE-KEY 摊还 O(1)，EXTRACT-MIN/DELETE 摊还 O(lg n)。
-
结构：根链表 + 树形堆 + 圆形双向链表（左右 sibling）；最小节点 H:min 直接指针访问；势函数 χ(H) = t(H) + 2m(H)，其中 t = 根数、m = 标记节点数。
-
关键操作：INSERT 加节点到根链表 O(1)；EXTRACT-MIN 时 consolidation 把同度根链合并（数组 A 按度数桶）→ 最坏 Θ(D(n)) 摊还。
-
DECREASE-KEY 用级联切除：新键违反堆序 → 把 x 切到根链表；若 y 已 mark 则递归切 y；这保证 mark 节点结构不乱。
-
最大度上界 D(n) = O(lg n)：引理 19.4 — size(x) ≥ F_{k+2} ≥ φ^k；故 k ≤ log_φ n = O(lg n)。这是 EXTRACT-MIN/DELETE 摊还 O(lg n) 的关键。
|
本章主旨
本章是数据结构设计「以摊还换最坏」的极致——斐波那契堆相比二叉堆在 INSERT/UNION/DECREASE-KEY 上各快一个 lg n 因子（由 O(lg n) 降到 O(1)），EXTRACT-MIN 持平 O(lg n)，但代价是常数因子大且程序复杂。理论上斐波那契堆的价值在于：让 Dijkstra 算法（第 24 章）从 O(V lg V + E lg V) 降到 O(V lg V + E)；让 MST Prim 算法（第 23 章）从 O(E lg V) 降到 O(E + V lg V)。但实际编程中很少用——太复杂。章末（19.4）通过 size(x) ≥ F_{k+2} ≥ φ^k 证明节点度的对数上界，这是不动点分析中的经典技巧。 |
一、核心概念
本章围绕 5 个核心概念展开：先建立 mergeable heap 抽象（19.1），再深入合并堆操作（19.2）、键值降低（19.3）、最大度上界（19.4）。
| 概念 | 定义 + 重要性 | 实现提示 |
|---|---|---|
Mergeable Heap 抽象 |
七操作：MAKE-HEAP, INSERT, MINIMUM, EXTRACT-MIN, UNION, DECREASE-KEY, DELETE — 最后一个不是 mergeable 自带但常需要。 |
§19.1 起；斐波那契堆 + 二叉堆比较表（图 19.1）。 |
斐波那契堆结构 |
根链表（圆形双向）+ 各树为最小堆序；节点属性 x.p, x.child, x.left, x.right, x.degree, x.mark。 |
§19.1;H:min 指针指向最小节点（root 之间也是循环双向链表）。 |
势函数 χ(H) = t(H) + 2m(H) |
t = 树数（根数）、m = 标记节点数；非空 H 的 χ ≥ 1（除非 H 空），初值 0、始终非负。 |
§19.1 式 19.1;用于 INSERT (Δ=1)、UNION (Δ=0)、EXTRACT-MIN (Δ=O(D(n))-t)、DECREASE-KEY (Δ≤4-c) 分析。 |
Consolidation |
EXTRACT-MIN 后把根链表按度合并；用数组 A[0..D(n)]；同度两根 → FIB-HEAP-LINK（小键作根，大键作子）；最终每度最多一棵树。 |
§19.2;CONSOLIDATE 伪代码 + 图 19.4 示例。 |
最大度 D(n) ≤ log_φ n |
size(x) ≥ F_{k+2} ≥ φ^k（引理 19.4），故度 = k 的节点至少占 φ^k 个元素；n 节点时 k ≤ log_φ n。 |
§19.4 详细证明；φ = (1+√5)/2；这意味着 EXTRACT-MIN 摊还 O(lg n)。 |
二、详细笔记
2.1 斐波那契堆结构与势函数
What：斐波那契堆是无序树集合 + 根链表 + 圆形双向链表，节点含 p/child/left/right/degree/mark 属性，H.min 指针指向最小节点。
Why：相比二叉堆（数组存储）它牺牲了结构紧凑性换取插入 / 合并 / 降键的常数摊还；势函数 χ = t + 2m 把「延迟工作」量化。
How：
| 节点属性 | 含义 | 取值范围 |
|---|---|---|
x.p |
父节点 |
NIL 表示 root |
x.child |
任意一个子节点 |
通过 left/right 访问兄弟 |
x.degree |
子节点数 |
≤ D(n) = O(lg n) |
x.mark |
自上次成为别人的子节点后是否丢过子节点 |
TRUE/FALSE |
H.min |
最小键所在的根节点 |
NIL 表示空 |
H.n |
节点总数 |
势函数（式 19.1）：\(\Phi(H) = t(H) + 2 m(H)\)，其中 t = 树数（根数）、m = 标记节点数。空堆 χ=0、始终 χ ≥ 0。
When：每当算法需要「插入频繁、合并频繁、降键频繁、但 EXTRACT-MIN 较少」的优先级队列——这是 Dijkstra、Prim 中 DECREASE-KEY 调用频繁的来源。
Example：CLRS 图 19.2 的斐波那契堆有 14 节点、5 棵树、3 个标记节点 → χ = 5 + 2·3 = 11。
2.2 合并堆操作 (MAKE / INSERT / MIN / UNION)
What：这四种操作摊还 O(1)——MAKE 直接初始化；INSERT 加到根链表并更新 H:min；MINIMUM 直接返回 H:min；UNION 把两堆根链表拼接。
Why：INSERT / UNION 是斐波那契堆设计的核心价值——把它们降到 O(1)，而二叉堆的 UNION 是 Θ(n)。代价：EXTRACT-MIN 变成「懒惰收集」从而摊还 O(D(n))。
How：
| 操作 | 摊还成本 |
|---|---|
实现关键 |
MAKE-FIB-HEAP |
O(1) |
分配对象、n=0、min=NIL → χ=0 |
FIB-HEAP-INSERT (lines 1-11) |
O(1) |
加到根链表；若 x.key < H.min.key 则更新 H.min；t+1、m 不变 → Δχ=+1 |
FIB-HEAP-MINIMUM |
O(1) |
返回 H.min |
FIB-HEAP-UNION (lines 1-7) |
O(1) |
拼接根链表（圆形双向连接）；重新设 H.min；t, m 累加 → Δχ=0 |
FIB-HEAP-EXTRACT-MIN |
O(D(n)) |
见 2.3 |
FIB-HEAP-DECREASE-KEY |
O(1) |
见 2.4 |
FIB-HEAP-DELETE |
O(D(n)) |
DECREASE-KEY + EXTRACT-MIN |
When：算法中 INSERT 操作占主体，偶尔需要 MIN / UNION；典型如 Dijkstra（INSERT 顶点 + DECREASE-KEY 边）+ Prim。
Example：7 个 INSERT 后根链表有 7 个孤立节点，t=7；EXTRACT-MIN 时做 CONSOLIDATE 把同度合并（若有同度），最终每度最多 1 棵树。
2.3 EXTRACT-MIN 与 Consolidation
What：删除最小节点 z → 其子节点全部进根链表 → 「consolidation」合并同度根（用数组 A 按度数桶）→ 重构 H.min；最坏 Θ(D(n) + t(H)) 时间、摊还 O(D(n))。
Why：EXTRACT-MIN 是斐波那契堆「最复杂」的操作——把平时累积的根链表合并为「度数互不相同」的紧致结构；势函数变化 t 增加但实际不变量强使摊还可控。
How：
-
FIB-HEAP-EXTRACT-MIN(H)：
-
z = H.min；若 z ≠ NIL：
-
把 z 的每个子节点接到根链表并清 p
-
从根链表中移除 z；若 z == z.right → 空堆 H.min=NIL；否则 H.min = z.right
-
CONSOLIDATE(H)
-
H.n -= 1;返回 z
-
-
CONSOLIDATE(H)：数组 A[0..D(H.n)] = NIL；遍历原根链表，对每个根 x：
-
d = x.degree；while A[d] ≠ NIL：y = A[d]；若 x.key > y.key：交换；FIB-HEAP-LINK(H, y, x)（y 变 x 的子，x.degree，y.mark=FALSE）；A[d] = NIL；d；A[d] = x。
-
遍历 A 非空位，把根接回根链表、找新 H.min。
-
-
FIB-HEAP-LINK(H, y, x)：从根链表中移除 y；y 变 x 的子节点；y.mark=FALSE。
摊还分析：实际 ≤ O(D(n) + t(H))；Δχ ≤ D(n) + 1 − t(H)；摊还 ≤ O(D(n))。
When：需要从优先队列取最小时；多用于 Dijkstra / Prim 的内层循环。
Example：CLRS 图 19.4 —— 14 节点堆提取最小节点 3；3 的 3 个子变根；9 个根做 consolidation；最终 t(H)=5、度互不相同（0,1,2,3）。
2.4 DECREASE-KEY 与级联切除
What：DECREASE-KEY(H, x, k) 把 x 的键降为 k；若违反堆序（x.key < x.p.key），把 x 切到根链表并 cascading-cut 处理父节点 mark 位。
Why：DECREASE-KEY 是 Dijkstra / Prim 性能的关键——若堆不支持 O(1) DECREASE-KEY，整个算法就退化为 O((V+E) lg V)；斐波那契堆用级联切除让 mark 节点结构受限，从而保证度数对数界。
How：
| 子操作 | 行为 |
|---|---|
摊还贡献 |
FIB-HEAP-DECREASE-KEY |
x.key = k；若违反 → CUT(H, x, x.p) + CASCADING-CUT(H, x.p) |
CUT(H, x, y) |
x 从 y 子链移除、x 进根链表、x.p=NIL、x.mark=FALSE；y.degree-- |
CASCADING-CUT(H, y) |
若 y.p 不空：若 y.mark=FALSE → y.mark=TRUE；否则 CUT(H, y, y.p) + 递归 CASCADING-CUT(H, y.p) |
H.min 更新 |
设切除次数为 c：势变化 Δχ ≤ c − (c−2) = 4−c → 摊还成本 ≤ O(c) + (4−c) = O(1)。
When：Dijkstra 中放松 (u, v) 时检查 dist[v]：若 d[u] + w(u,v) < dist[v]，则 DECREASE-KEY(H, v, d[u]+w(u,v))；原书分析依赖 DECREASE-KEY 摊还 O(1)。
Example：CLRS 图 19.5 —— 键 46 → 15 时节点切到根，父 24 标 mark；键 35 → 5 时节点切到根，父 26 已 mark → cascading-cut：26 切到根并清 mark，父 24 也 mark → cascading-cut 再切 24；最终 24 切到根但 7 是 root 所以停。
2.5 最大度上界 D(n) ≤ log_φ n
What：节点度数为 k 的斐波那契堆节点 size(x) ≥ F_{k+2} ≥ φ^k，故 n 节点时 D(n) ≤ log_φ n = O(lg n)。
Why：EXTRACT-MIN 摊还 O(D(n)) 必须有 D(n) = O(lg n) 才能说 EXTRACT-MIN 摊还 O(lg n)。这是斐波那契堆「名字的由来」（φ ≈ 1.618 是黄金比）。
How：
-
引理 19.1：若 x 的度为 k、子节点按接入顺序为 y₁…y_k，则 y₁.degree ≥ 0 且 yᵢ.degree ≥ i−2（i ≥ 2）——因接入时 yᵢ 与 x 有相同度，而后续最多丢 1 子。
-
引理 19.2 (Fibonacci 求和)：F_{k+2} = 1 + Σᵢ₌₀ᵏ Fᵢ。
-
引理 19.3：F_{k+2} ≥ φ^k。
-
引理 19.4：size(x) ≥ F_{k+2} ≥ φ^k。
-
推论 19.5：D(n) = O(lg n)。
When：证明 EXTRACT-MIN、DELETE 摊还 O(lg n) 的引理 19.4 是必需——它是斐波那契堆理论分析的「收官之笔」。
Example：F₀=0, F₁=1, F₂=2, F₃=3, F₄=5, F₅=8 → φ² ≈ 2.618、F₄ = 5；φ¹⁰ ≈ 122.99、F₁₂ = 233。size 增长速度比 φ^k 还快。
三、关键图表
|
核心公式对照表
|
四、思维导图
mindmap
root((第 19 章 斐波那契堆))
结构
根链表
圆形双向
节点域p/child
度mark
势函数
t+2m
始终非负
合并堆操作
MAKE O1
INSERT O1
MINIMUM O1
UNION O1
EXTRACT-MIN
子节点进根链表
consolidation
数组A按度桶
摊还O(lgn)
DECREASE-KEY
CUT
级联切除
mark机制
摊还O1
最大度上界
F_{k+2}≥φ^k
D(n)≤log_φ n
名称来源
与二叉堆对比
合并O1 vs Θn
插入O1 vs lgn
提取持平
应用
Dijkstra
Prim
复杂度降一档
== 五、重点与易错点
. INSERT / UNION 的摊还 O(1) 是关键——但工程中常数因子大，所以实践中少用。
. EXTRACT-MIN 不写 UNION 操作：UNION 是「两步拼接根链表」，EXTRACT-MIN 是「consolidate 同度节点」，两者独立。
. 标记节点 mark 的语义：「自上次成为别人的子节点后是否丢过子节点」——一旦再被接到别人，立刻清 mark（CUT line 4）。
. 级联切除只在父节点已经 mark 时触发——不是「丢子节点即切」。
. D(n) ≤ log_φ n 的引理 19.4 必须用 size 子树而非「自我递归」——这是斐波那契堆「度有界」的关键证据。
. 不支持 SEARCH 操作——找节点需要指针（如 Fibonacci-Heap-Handle 模式）——这是为何 Dijkstra / Prim 需要外部维护顶点句柄。
. MAKE-HEAP / MINIMUM 没有「键比较」——直接返回 H:min（O(1)）。
. 「EXTRACT-MIN 摊还 O(D(n)) = O(lg n)」的推导：D(n) + t(H) 实际成本上限；Δχ ≤ D(n) + 1 − t(H)；幅度差是 (D(n) − t(H)) + 1，由 −t(H) 抵消前期根数。
. chapter notes 提到的 relaxed heaps（Driscoll-Gabow-Shrairman-Tarjan）有更优最坏（不是摊还）界：D/in O(1) worst-case, E/M/D O(lg n) worst-case。
. Fibonacci 堆理论价值 > 实用价值——实践中常用 k-ary heap（d-ary heap）平衡常数因子与渐近界。
. H.min 是 min 指针，不需要搜索——但若多个根同键，则 H.min 取任意一个；EXTRACT-MIN 后 H.min 重新扫描定位。
. H.n 在 INSERT / EXTRACT-MIN / DELETE 中各 ±1；MAKE-HEAP n=0。
. 在第 24 章 Dijkstra 中：INITIALIZE-SINGLE-SOURCE 设 d[v]=∞（D-ary heap）或用 Fibonacci-Heap-Insert 首次插入——后者总 O(V) 摊还。