元信息：Cormen, Leiserson, Rivest, Stein《Introduction to Algorithms》（第 3 版）｜作者：T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein｜本笔记负责 PDF 第 450–666 页（原书页码 p.429–645，PDF 页码 = 原书页码 + 21）。覆盖：第 16 章后半（16.3 Huffman 编码起）、第 17 章摊还分析、第 V 部分高级数据结构（第 18–21 章）、第 VI 部分图算法（第 22、23 章及第 24 章开头）。

第 16 章 贪心算法（Greedy Algorithms）（PDF p.450–471，接上一块）

16.3 Huffman 编码（Huffman codes）（PDF p.450–458，接上一块）

问题背景。 用二进制串表示字符，每个字符对应唯一的码字（codeword）。原书例子：一个 100,000 字符的数据文件，只含 a–f 六个字符，频率（千次）为 a:45, b:13, c:12, d:16, e:9, f:5。

• 定长码（fixed-length code）：6 个字符需 3 位，总长 300,000 位。
• 变长码（variable-length code）：高频字符用短码，低频用长码。总长 \((45\cdot1+13\cdot3+12\cdot3+16\cdot3+9\cdot4+5\cdot4)\times1000=224{,}000\) 位，节省约 25%，而且这正是该文件的最优字符编码。

前缀码（prefix code）。 任何码字都不是另一码字的前缀（更准确的名字是"无前缀码 prefix-free code"，但"前缀码"是标准术语）。书中不加证明地指出：前缀码总能达到所有字符编码中的最优压缩，所以只研究前缀码不失一般性。

• 编码：直接把各字符码字拼接，如 abc → 0·101·100 = 0101100。
• 解码：由于没有码字是其他码字的前缀，文件开头的码字是唯一确定的；识别出第一个码字、翻译、对剩余部分重复。例：001011101 唯一地分解为 0·0·101·1101，解码为 aabe。

码树表示。 用一棵叶子为字符的二叉树表示前缀码：从根到叶子的简单路径就是码字，0 表示走左孩子，1 表示走右孩子（这不是二叉搜索树，叶子不必有序，内部结点不存字符）。

• 最优编码总对应一棵满二叉树（full binary tree，每个非叶结点恰有两个孩子；习题 16.3-2）。定长码不最优：它的树中有以 10… 开头的码字，却没有以 11… 开头的，因此不是满二叉树。
• 若字母表为 \(C\) 且所有频率为正，最优前缀码的树恰有 \(|C|\) 个叶子、\(|C|-1\) 个内部结点。
• 记 \(c.freq\) 为字符频率，\(d_T(c)\) 为 \(c\) 的叶子在树 \(T\) 中的深度（也即码字长度），则编码文件所需位数（树的代价 cost）为
  \[B(T)=\sum_{c\in C} c.freq\cdot d_T(c). \tag{16.4}\]

Huffman 算法。 自底向上构造：从 \(|C|\) 个叶子出发，执行 \(|C|-1\) 次"合并"。用以 freq 为键的最小优先队列 \(Q\) 找出频率最低的两个对象合并，新对象频率为两者之和。

def HUFFMAN(C):                 # C: 字符集合，每个 c 有 c.freq
    n = len(C)
    Q = MinPriorityQueue(C)     # 以 freq 为键；BUILD-MIN-HEAP，O(n)
    for i in range(1, n):       # 共 n-1 次合并
        z = Node()
        z.left  = x = Q.extract_min()
        z.right = y = Q.extract_min()
        z.freq  = x.freq + y.freq
        Q.insert(z)
    return Q.extract_min()      # 返回码树的根

• 例子（图 16.5）：初始队列按频率 f:5, e:9, c:12, b:13, d:16, a:45。依次合并 f+e=14；c+b=25；14+d=30；25+30=55；a+55=100，最终树给出 a=0, c=100, b=101, f=1100, e=1101, d=111。左右孩子的顺序是任意的，交换任一结点的左右孩子得到代价相同的另一种编码。
• 复杂度：\(Q\) 用二叉最小堆，初始化 \(O(n)\)，循环 \(n-1\) 次、每次堆操作 \(O(\lg n)\)，总时间 \(O(n\lg n)\)；若改用 van Emde Boas 树（第 20 章，要求频率为有界整数）可降到 \(O(n\lg\lg n)\)。空间 \(O(n)\)（树有 \(2n-1\) 个结点）。

正确性：贪心选择性质。

引理 16.2：设 \(x,y\) 是 \(C\) 中频率最低的两个字符，则存在一个最优前缀码，其中 \(x\) 与 \(y\) 的码字长度相同且只在最后一位不同。

证明思路（交换论证 exchange argument）：取任一最优树 \(T\)，设 \(a,b\) 为最大深度的一对兄弟叶子，不妨 \(a.freq\le b.freq\)、\(x.freq\le y.freq\)，于是 \(x.freq\le a.freq\)，\(y.freq\le b.freq\)。若 \(x.freq=b.freq\)，则四者频率全相等（习题 16.3-1），引理平凡成立，故设 \(x\ne b\)。在 \(T\) 中交换 \(a\) 与 \(x\) 得 \(T'\)，再交换 \(b\) 与 \(y\) 得 \(T''\)（若 \(x=b\) 而 \(y\ne a\)，\(T''\) 中 \(x,y\) 就不是最大深度兄弟，这正是排除 \(x=b\) 的原因）。

为什么这是"贪心"：把一次合并的代价看作被合并两项频率之和；树的总代价等于所有合并代价之和（习题 16.3-4）。每一步 HUFFMAN 都选当前代价最小的合并。

正确性：最优子结构。

引理 16.3：设 \(x,y\) 频率最小，\(C'=C-\{x,y\}\cup\{z\}\)，\(z.freq=x.freq+y.freq\)。若 \(T'\) 是 \(C'\) 的最优前缀码树，则把 \(T'\) 中叶子 \(z\) 替换成以 \(x,y\) 为孩子的内部结点所得的 \(T\)，是 \(C\) 的最优前缀码树。

证明：对 \(c\in C-\{x,y\}\)，\(d_T(c)=d_{T'}(c)\)；\(d_T(x)=d_T(y)=d_{T'}(z)+1\)，所以

定理 16.4：HUFFMAN 产生最优前缀码（由引理 16.2、16.3 直接得到）。

常见误区：码树不是 BST；Huffman 只在"逐字符编码"类中最优；频率相同时的平局可任意打破，得到的码字不同但代价相同。

习题 16.3（PDF p.457–458）概括：16.3-1 补全引理 16.2 证明中的等号情形；16.3-2 证明非满二叉树不可能最优；16.3-3 以前 8 个 Fibonacci 数（1,1,2,3,5,8,13,21）为频率求 Huffman 码并推广到前 \(n\) 个 Fibonacci 数（得到"一条链"形的树）；16.3-4 证明树代价 = 所有内部结点两个孩子频率之和；16.3-5 频率单调递减时存在码长单调递增的最优码；16.3-6 用 \(2n-1+n\lceil\lg n\rceil\) 位传输一个最优前缀码（用一次树遍历的 \(2n-1\) 位描述结构）；16.3-7 推广到三进制码；16.3-8 256 个字符频率接近（最大频率 < 2 倍最小频率）时 Huffman 不比 8 位定长码好；16.3-9 用计数论证说明随机 8 位字符文件不可能期望压缩哪怕 1 位。

16.4 拟阵与贪心方法（Matroids and greedy methods）（PDF p.458–464，带星号选读节）

本节概述一个刻画"何时贪心可得最优解"的理论。它不能覆盖所有贪心问题（例如不覆盖 16.1 的活动选择和 16.3 的 Huffman），但覆盖许多实际情形。

拟阵定义。 拟阵（matroid）是有序对 \(M=(S,\mathcal I)\)，满足：

1. \(S\) 是有限集；
2. \(\mathcal I\) 是 \(S\) 的非空子集族，称为独立子集（independent subsets），并满足遗传性（hereditary）：若 \(B\in\mathcal I\) 且 \(A\subseteq B\)，则 \(A\in\mathcal I\)。因此 \(\varnothing\in\mathcal I\)；
3. 交换性质（exchange property）：若 \(A,B\in\mathcal I\) 且 \(|A|<|B|\)，则存在 \(x\in B-A\) 使 \(A\cup\{x\}\in\mathcal I\)。

例子：

• 矩阵拟阵（matric matroid，Whitney 命名由来）：\(S\) 为矩阵的行（或列），线性无关的行集为独立集（习题 16.4-2）。
• 图拟阵（graphic matroid）\(M_G=(S_G,\mathcal I_G)\)：对无向图 \(G=(V,E)\)，\(S_G=E\)；边集 \(A\) 独立当且仅当 \(A\) 无环，即 \(G_A=(V,A)\) 是森林。与最小生成树密切相关。

定理 16.5：\(M_G\) 是拟阵。证明：\(E\) 有限；森林的子集仍是森林（遗传性）。交换性：先证森林 \(F=(V_F,E_F)\) 恰含 \(|V_F|-|E_F|\) 棵树——若第 \(i\) 棵树有 \(v_i\) 个顶点和 \(e_i=v_i-1\) 条边，则 \(|E_F|=\sum(v_i-1)=|V_F|-t\)。于是 \(G_A\) 有 \(|V|-|A|\) 棵树，\(G_B\) 有 \(|V|-|B|\) 棵树，\(|B|>|A|\) 意味着 \(G_B\) 树更少，必有 \(G_B\) 中某棵树 \(T\) 的顶点落在 \(G_A\) 的两棵不同树中；\(T\) 连通，故含一条边 \((u,v)\) 的两端分属 \(G_A\) 的不同树，把它加入 \(A\) 不成环。

扩张与极大独立集。 若 \(x\notin A\) 且 \(A\cup\{x\}\in\mathcal I\)，称 \(x\) 是 \(A\) 的扩张（extension）。在图拟阵中，\(e\) 是 \(A\) 的扩张当且仅当 \(e\notin A\) 且加入后不成环。没有扩张的独立集称极大（maximal）。

定理 16.6：拟阵中所有极大独立子集大小相同。（反证：若 \(B\) 比极大的 \(A\) 大，交换性给出 \(A\) 的扩张，矛盾。）在连通图的图拟阵中，极大独立集就是恰有 \(|V|-1\) 条边的生成树（spanning tree）。

加权拟阵。 赋予每个 \(x\in S\) 严格正权 \(w(x)\)，\(w(A)=\sum_{x\in A}w(x)\)。目标：找权最大的独立集，称为最优子集（optimal subset）。权为正，所以最优子集必是极大独立集。

最小生成树化归：给定边长 \(w(e)\)，取 \(w_0\) 大于最大边长，令 \(w'(e)=w_0-w(e)>0\)。对极大独立集（生成树，\(|V|-1\) 条边）

通用贪心算法。

def GREEDY(M, w):
    A = set()
    for x in sorted(M.S, key=w, reverse=True):   # 按权单调递减
        if is_independent(A | {x}):              # 独立性检查，设耗时 O(f(n))
            A.add(x)
    return A

• 由归纳，\(A\) 始终独立。
• 复杂度：排序 \(O(n\lg n)\)，独立性检查共 \(n\) 次，总时间 \(O(n\lg n+n f(n))\)，\(n=|S|\)。

正确性证明链。

• 引理 16.7（贪心选择性质）：\(S\) 按权递减排序，令 \(x\) 为第一个使 \(\{x\}\) 独立的元素；若 \(x\) 存在，则存在包含 \(x\) 的最优子集。证明：取任一非空最优子集 \(B\)，设 \(x\notin B\)。对 \(y\in B\)，\(\{y\}\) 独立（遗传性），按 \(x\) 的选取有 \(w(x)\ge w(y)\)。从 \(A=\{x\}\) 开始，用交换性不断从 \(B\) 中加元素直到 \(|A|=|B|\)，于是 \(A=B-\{y\}\cup\{x\}\)，\(w(A)=w(B)-w(y)+w(x)\ge w(B)\)，\(A\) 也最优。
• 引理 16.8：若 \(x\) 是某个独立集 \(A\) 的扩张，则 \(x\) 也是 \(\varnothing\) 的扩张（遗传性）。推论 16.9（逆否）：若 \(x\) 不是 \(\varnothing\) 的扩张，它不是任何独立集的扩张——一开始用不上的元素永远用不上，GREEDY 跳过它们不会出错。
• 引理 16.10（最优子结构）：GREEDY 选出第一个元素 \(x\) 后，剩下的问题化为在收缩（contraction）\(M'=(S',\mathcal I')\) 上求最大权独立集，其中 \(S'=\{y\in S:\{x,y\}\in\mathcal I\}\)，\(\mathcal I'=\{B\subseteq S-\{x\}:B\cup\{x\}\in\mathcal I\}\)，权函数限制到 \(S'\)。因为两边一一对应且 \(w(A)=w(A')+w(x)\)。
• 定理 16.11：GREEDY 在加权拟阵上返回最优子集（综合上面三条）。

习题 16.4（PDF p.464）概括：16.4-1 证明"大小不超过 \(k\) 的子集族"（均匀拟阵 uniform matroid）是拟阵；16.4-2 矩阵列的线性无关集构成拟阵；16.4-3 对偶拟阵：独立集为"补集包含某极大独立集"的集合；16.4-4 划分拟阵（partition matroid）：每个块至多取一个；16.4-5 如何把"最小权极大独立集"问题转成标准加权拟阵问题。

16.5 用拟阵解任务调度问题（A task-scheduling problem as a matroid）（PDF p.464–467，选读节）

问题。 单处理器上调度单位时间任务（unit-time task），每个任务有截止时间和误期罚款：

• 任务集 \(S=\{a_1,\dots,a_n\}\)，每个耗时 1；调度（schedule）是 \(S\) 的一个排列，第 1 个任务在 \([0,1]\) 执行，依次类推；
• 整数截止时间 \(d_1,\dots,d_n\)，\(1\le d_i\le n\)，任务 \(a_i\) 应在 \(d_i\) 前完成；
• 非负罚款 \(w_1,\dots,w_n\)：\(a_i\) 未在 \(d_i\) 前完成则罚 \(w_i\)。
• 目标：最小化总罚款。

规范化。 在某调度中，完成时间晚于截止时间的任务叫迟的（late），否则叫早的（early）。

• 早任务优先形式（early-first form）：若早任务 \(a_i\) 排在迟任务 \(a_j\) 后，交换两者，\(a_i\) 仍早、\(a_j\) 仍迟。
• 规范形式（canonical form）：早任务在前，且早任务按截止时间单调递增排列。若相邻两个早任务 \(a_i,a_j\) 在时刻 \(k,k+1\) 完成且 \(d_j<d_i\)，交换：因 \(k+1\le d_j<d_i\)，\(a_i\) 仍早；\(a_j\) 提前，也仍早。
• 因此问题化为：选出一个早任务集合 \(A\)，按截止时间递增排 \(A\)，再任意排 \(S-A\)。

独立性。 若存在使集合 \(A\) 中无任务迟到的调度，称 \(A\) 独立。记 \(N_t(A)\) 为 \(A\) 中截止时间 \(\le t\) 的任务数，\(N_0(A)=0\)。

引理 16.12：下列等价：(1) \(A\) 独立；(2) 对 \(t=0,1,\dots,n\)，\(N_t(A)\le t\)；(3) 把 \(A\) 按截止时间递增调度，没有任务迟到。证明：(1)⇒(2) 用逆否命题，若 \(N_t(A)>t\)，有多于 \(t\) 个任务必须在时刻 \(t\) 前完成，不可能；(2)⇒(3)：按截止时间递增排时不会"卡住"，因为 (2) 意味着排序后第 \(i\) 个任务的截止时间至少为 \(i\)，而它恰在时刻 \(i\) 完成；(3)⇒(1) 显然。用性质 (2) 可在 \(O(|A|)\) 时间判定独立性（习题 16.5-2，用计数数组统计每个截止时间的任务数再做前缀和）。

最小化迟任务罚款之和 ⟺ 最大化早任务罚款之和。

定理 16.13：\((S,\mathcal I)\) 是拟阵。证明交换性：设 \(|B|>|A|\)，令 \(k\) 为满足 \(N_t(B)\le N_t(A)\) 的最大 \(t\)（\(t=0\) 时成立，故存在）。由 \(N_n(B)=|B|>|A|=N_n(A)\)，\(k<n\) 且对 \(k+1\le j\le n\) 有 \(N_j(B)>N_j(A)\)，所以 \(B\) 中截止时间为 \(k+1\) 的任务比 \(A\) 多，取其中 \(a_i\in B-A\)，令 \(A'=A\cup\{a_i\}\)。对 \(t\le k\)，\(N_t(A')=N_t(A)\le t\)；对 \(t>k\)，\(N_t(A')\le N_t(B)\le t\)。故 \(A'\) 独立。

算法与复杂度。 对罚款为权的拟阵运行 GREEDY：按罚款递减考察任务，能保持独立就加入。每次独立性检查 \(O(n)\)，共 \(O(n)\) 次，总 \(O(n^2)\)；思考题 16-4 用不相交集合森林给出更快实现。

例题（图 16.7）：

贪心依次接受 \(a_1,a_2,a_3,a_4\)；拒绝 \(a_5\)（\(N_4(\{a_1..a_5\})=5>4\)）和 \(a_6\)（同理 \(N_4=5\)）；接受 \(a_7\)。最优调度为 \(\langle a_2,a_4,a_1,a_3,a_7,a_5,a_6\rangle\)，总罚款 \(w_5+w_6=50\)。

习题 16.5 概括：16.5-1 把罚款改为 \(80-w_i\) 重解该实例；16.5-2 \(O(|A|)\) 判定独立性。

第 16 章思考题（Problems）（PDF p.467–470）

• 16-1 找零（Coin changing）：(a) 用 25、10、5、1 美分硬币找零的贪心算法及最优性证明；(b) 面额为 \(c^0,c^1,\dots,c^k\) 时贪心最优；(c) 构造贪心不最优的面额集合（须含 1 美分），如 {1, 3, 4} 找 6；(d) 任意 \(k\) 种面额的 \(O(nk)\) 动态规划。
• 16-2 最小化平均完成时间：任务 \(a_i\) 需处理时间 \(p_i\)，完成时间 \(c_i\)，最小化 \(\frac1n\sum c_i\)。例：\(p_1=3,p_2=5\)，先 \(a_2\) 平均 6.5，先 \(a_1\) 平均 5.5。(a) 非抢占：最短处理时间优先（SPT）；(b) 有释放时间 \(r_i\) 且允许抢占：最短剩余处理时间优先（SRPT）。
• 16-3 无环子图：(a) 无向图关联矩阵（incidence matrix）在模 2 域上列线性无关 ⟺ 对应边集无环；(b) 求最大权无环边子集（即最大生成森林，用 GREEDY/Kruskal）；(c) 有向图"不含有向环的边集"一般不构成拟阵，举反例并指出哪条公理失败；(d) 有向图关联矩阵（离开 \(-1\)、进入 \(+1\)）列线性无关 ⇒ 无有向环；(e) 解释 (c) 与 (d) 为何不矛盾。
• 16-4 调度变体：按罚款递减处理任务，把每个任务放进其截止时间之前最晚的空槽，没有就放进最晚的空槽。(a) 证明最优；(b) 用 21.3 节不相交集合森林高效实现（近线性时间）。
• 16-5 离线缓存（Off-line caching）：请求序列 \(\langle r_1,\dots,r_n\rangle\)，缓存大小 \(k\)，缓存未命中（cache miss）时须决定驱逐谁。离线版本已知全部请求，贪心策略最远将来（furthest-in-future）：驱逐下次访问最远的元素。(a) 写伪代码并分析时间；(b) 证明最优子结构；(c) 证明该策略未命中数最少。

本章注记（PDF p.471）：更多贪心与拟阵内容见 Lawler、Papadimitriou–Steiglitz；拟阵贪心算法首见于 Edmonds 1971，拟阵理论源于 Whitney 1935；Huffman 码发明于 1952；Korte 与 Lovász 把拟阵推广为贪心拟阵（greedoid）。

第 16 章（本块覆盖部分）本章要点

• 贪心算法正确性的两根支柱：贪心选择性质（存在包含贪心选择的最优解，常用交换论证证明）+ 最优子结构（做出选择后剩余问题与原问题同型）。
• Huffman 编码：反复合并频率最小的两棵树，\(O(n\lg n)\)；树代价 \(B(T)=\sum c.freq\cdot d_T(c)\) 等于所有合并代价之和。
• 拟阵 \((S,\mathcal I)\)：遗传性 + 交换性。加权拟阵上"按权递减、能加就加"的 GREEDY 必得最优；极大独立集等大。图拟阵对应生成森林，任务调度（单位时间、截止时间、罚款）也是拟阵。

与量化交易的关联

• Huffman/前缀码：行情数据压缩与二进制协议设计的理论基础。高频行情（tick、逐笔委托）存储和网络传输中会用熵编码类压缩；理解"按频率分配码长"有助于设计自定义报文字段编码，但实际系统多用通用压缩库（zstd、LZ4），直接手写 Huffman 的场景少。
• 拟阵与贪心：组合选股中，若约束结构是拟阵（例如"每个行业至多选 1 只"是划分拟阵，"最多选 \(k\) 只"是均匀拟阵），按信号强度从高到低贪心选取就能得到加权和最大的组合；一旦约束不是拟阵（如资金/容量背包约束、换手率约束），贪心不再保证最优，需整数规划。这个判别对快速写组合构建启发式很有用。
• 带截止时间与罚款的单位任务调度：可类比为批处理回测任务、盘后数据作业在固定时间窗内的调度；离线缓存的"最远将来"策略是缓存淘汰的理论最优基准，可用来评估 LRU 等在线策略在因子数据缓存上的差距。

推荐习题

• 16.3-3（Fibonacci 频率的 Huffman 树，理解最坏情况码长）；16.3-4（树代价 = 合并代价之和）；16.3-8/16.3-9（压缩的极限，计数论证）。
• 16.4-2、16.4-4（矩阵拟阵、划分拟阵的验证）；16.4-5（最小权极大独立集的转化）。
• 16.5-2（\(O(|A|)\) 独立性检验）。
• 思考题 16-1（找零：贪心何时失败）、16-2（SPT/SRPT 调度）、16-5（离线缓存最优性证明）。

第 17 章 摊还分析（Amortized Analysis）（PDF p.472–499）

17.0 本章导言（PDF p.472–473）

摊还分析（amortized analysis）：把一串数据结构操作所需的时间在所有操作上平均。即使序列中某个操作很昂贵，平均到整串上每个操作的代价也可能很小。

• 与平均情况分析（average-case analysis）不同：摊还分析不涉及概率，它保证的是最坏情况下每个操作的平均性能。
• 三种常用方法：聚合分析（aggregate analysis，17.1）——求 \(n\) 个操作总代价上界 \(T(n)\)，每个操作摊还代价为 \(T(n)/n\)，所有操作类型摊还代价相同；核算法（accounting method，17.2）——给不同操作类型设定不同摊还代价，早期多收的费用作为"预付信用"（credit）存放在数据结构中的特定对象上；势能法（potential method，17.3）——与核算法类似，但把信用作为整个数据结构的"势能"（potential）来维护。
• 两个贯穿例子：带 MULTIPOP 的栈；从 0 开始只做 INCREMENT 的二进制计数器。17.4 用势能法分析动态扩张/收缩的表。
• 重要提醒：摊还分析中赋予的费用只用于分析，不需要（也不应该）出现在代码里，比如不必真的维护 x.credit 字段。

17.1 聚合分析（Aggregate analysis）（PDF p.473–477）

聚合分析：证明对所有 \(n\)，任意 \(n\) 个操作的序列最坏总时间为 \(T(n)\)，则每个操作的摊还代价为 \(T(n)/n\)（对序列中各种操作类型都一样）。

例 1：栈操作。 PUSH(S, x)、POP(S) 各 \(O(1)\)，记代价为 1。新增 MULTIPOP(S, k)：弹出栈顶 \(k\) 个对象，栈中不足 \(k\) 个则全部弹出。

def MULTIPOP(S, k):
    while not S.empty() and k > 0:
        S.pop()
        k -= 1

• 对含 \(s\) 个对象的栈，MULTIPOP 实际代价为 \(\min(s,k)\)。例（图 17.1）：栈自顶为 23,17,6,39,10,47，MULTIPOP(S,4) 后剩 10,47；再 MULTIPOP(S,7) 清空。
• 粗略分析：单个 MULTIPOP 最坏 \(O(n)\)，\(n\) 个操作 \(O(n^2)\)——正确但不紧。
• 聚合分析：每个对象每被压入一次至多被弹出一次，所以非空栈上 POP（含 MULTIPOP 内部的）调用次数 ≤ PUSH 次数 ≤ \(n\)。任意 \(n\) 个 PUSH/POP/MULTIPOP 总代价 \(O(n)\)，摊还代价 \(O(1)\)。强调：没有用概率推理，这是最坏情况界。

例 2：\(k\) 位二进制计数器。 数组 \(A[0..k-1]\)，\(A[0]\) 为最低位，\(x=\sum_{i=0}^{k-1}A[i]\cdot2^i\)，初值 0，INCREMENT 对 \(2^k\) 取模加 1。

def INCREMENT(A):
    i = 0
    while i < len(A) and A[i] == 1:   # 进位：把末尾连续的 1 翻成 0
        A[i] = 0
        i += 1
    if i < len(A):
        A[i] = 1

• 代价 = 翻转的位数。粗略：最坏单次 \(\Theta(k)\)（全 1），\(n\) 次 \(O(nk)\)。
• 聚合：\(A[0]\) 每次都翻，\(A[1]\) 每 2 次翻一次（共 \(\lfloor n/2\rfloor\) 次），\(A[i]\) 共翻 \(\lfloor n/2^i\rfloor\) 次；\(i\ge k\) 的位不存在。总翻转
  \[\sum_{i=0}^{k-1}\left\lfloor\frac{n}{2^i}\right\rfloor<n\sum_{i=0}^{\infty}\frac1{2^i}=2n.\]
  所以 \(n\) 次 INCREMENT 最坏 \(O(n)\)，摊还 \(O(1)\)。图 17.2 显示 0 到 16 的累计代价（1,3,4,7,8,10,11,15,16,18,19,22,23,25,26,31），总代价始终小于操作次数的两倍。

习题 17.1 概括：17.1-1 加入 MULTIPUSH（一次压 \(k\) 个）后 \(O(1)\) 摊还界不再成立（每次 MULTIPUSH 代价 \(k\)）；17.1-2 加入 DECREMENT 后 \(n\) 次操作可达 \(\Theta(nk)\)（在 \(2^{k-1}\) 附近来回加减）；17.1-3 第 \(i\) 个操作当 \(i\) 为 2 的幂时代价为 \(i\)，否则 1，用聚合分析求摊还代价（总代价 \(<3n\)，摊还 \(O(1)\)）。

17.2 核算法（The accounting method）（PDF p.477–480）

思想。 给不同操作设定不同的收费，称为其摊还代价 \(\hat c_i\)。若摊还代价超过实际代价 \(c_i\)，差额作为信用（credit）存到数据结构的特定对象上，供以后摊还代价低于实际代价的操作使用。要求对所有长度为 \(n\) 的操作序列

栈例子。 实际代价：PUSH 1，POP 1，MULTIPOP \(\min(k,s)\)。设摊还代价：PUSH 2，POP 0，MULTIPOP 0（摊还代价可以是常数，即使实际代价可变；不同操作的摊还代价甚至可以渐近不同）。

• 类比：用 1 美元代表单位代价，自助餐厅的一摞盘子。压入一个盘子付 2 美元：1 美元支付压栈，1 美元作为信用放在盘子上。任何时刻栈中每个盘子上都有 1 美元。
• POP 或 MULTIPOP 弹出盘子时用盘子上那 1 美元支付，自身收费 0。
• 栈中盘子数非负，因此信用非负。\(n\) 个操作摊还总代价 \(O(n)\)，故实际总代价 \(O(n)\)。

计数器例子。 代价 = 翻转位数。把一位置 1 收费 2 美元：1 美元付置位，1 美元作为信用留在该位上，用于以后把它复位为 0。于是复位不收费。每次 INCREMENT 至多置位一次（第 6 行），摊还代价 ≤ 2。计数器中 1 的个数非负，信用非负，\(n\) 次 INCREMENT 总代价 \(O(n)\)。

习题 17.2 概括：17.2-1 栈大小不超过 \(k\)，每 \(k\) 个操作做一次全栈备份拷贝，用核算法证明 \(n\) 个操作含拷贝代价为 \(O(n)\)（每个操作多收 1 美元存起来付拷贝）；17.2-2 用核算法重做 17.1-3；17.2-3 计数器同时支持 INCREMENT 与 RESET（全部清零），维护指向最高位 1 的指针，使 \(n\) 个操作为 \(O(n)\)。

17.3 势能法（The potential method）（PDF p.480–484）

定义。 对初始数据结构 \(D_0\) 执行 \(n\) 个操作，第 \(i\) 个操作实际代价 \(c_i\)，结果为 \(D_i\)。势函数（potential function）\(\Phi\) 把每个 \(D_i\) 映射为实数 \(\Phi(D_i)\)。第 \(i\) 个操作关于 \(\Phi\) 的摊还代价

• 若 \(\Phi(D_n)\ge\Phi(D_0)\)，摊还总代价就是实际总代价的上界。由于事先不知道会执行多少个操作，通常要求对所有 \(i\)，\(\Phi(D_i)\ge\Phi(D_0)\)；惯例是令 \(\Phi(D_0)=0\) 并证明 \(\Phi(D_i)\ge0\)（若 \(\Phi(D_0)\ne0\) 的处理见习题 17.3-1）。
• 直观：势能差为正 → 该操作被多收费，势能上升；为负 → 少收费，势能下降支付实际代价。
• 摊还代价依赖于势函数的选择；不同势函数给出不同但都有效的上界，选取时常有权衡。

栈： \(\Phi\) = 栈中对象数，\(\Phi(D_0)=0\)，\(\Phi(D_i)\ge0\)。

• PUSH：势能差 \((s+1)-s=1\)，\(\hat c=1+1=2\)。
• MULTIPOP(S,k)：弹出 \(k'=\min(k,s)\) 个，实际代价 \(k'\)，势能差 \(-k'\)，\(\hat c=k'-k'=0\)；POP 同理为 0。
• 三种操作摊还 \(O(1)\)，\(n\) 个操作最坏 \(O(n)\)。

计数器： \(\Phi\) = 第 \(i\) 次操作后计数器中 1 的个数 \(b_i\)。设第 \(i\) 次 INCREMENT 复位 \(t_i\) 位，实际代价 ≤ \(t_i+1\)。若 \(b_i=0\)，说明复位了全部 \(k\) 位，\(b_{i-1}=t_i=k\)；若 \(b_i>0\)，\(b_i=b_{i-1}-t_i+1\)。总之 \(b_i\le b_{i-1}-t_i+1\)，

不从 0 开始的计数器。 初始有 \(b_0\) 个 1，结束有 \(b_n\) 个 1，\(0\le b_0,b_n\le k\)。改写 (17.3)：

习题 17.3 概括：17.3-1 \(\Phi(D_0)\ne0\) 时构造 \(\Phi'=\Phi-\Phi(D_0)\)；17.3-2 用势能法重做 17.1-3；17.3-3 为二叉最小堆设计势函数，使 INSERT 摊还 \(O(\lg n)\)、EXTRACT-MIN 摊还 \(O(1)\)（如 \(\Phi=\sum\) 各元素所在深度相关的量，或 \(\Phi=n\lg n\) 类）；17.3-4 栈从 \(s_0\) 个对象开始、以 \(s_n\) 个结束时 \(n\) 个操作的总代价（\(\le 2n - s_n + s_0\) 量级）；17.3-5 计数器初始有 \(b\) 个 1，\(n=\Omega(b)\) 时总代价 \(O(n)\)；17.3-6 两个栈实现队列，ENQUEUE、DEQUEUE 摊还 \(O(1)\)；17.3-7 支持 INSERT 与 DELETE-LARGER-HALF（删除最大的 \(\lceil|S|/2\rceil\) 个元素）的数据结构，\(m\) 个操作 \(O(m)\)（用无序数组 + 线性时间选择中位数）。

17.4 动态表（Dynamic tables）（PDF p.484–492）

问题。 事先不知道要存多少对象：表满时需重新分配更大的表并复制全部对象；大量删除后可能值得缩小表。目标：插入、删除摊还代价 \(O(1)\)，且未用空间不超过总空间的常数比例。

• 支持 TABLE-INSERT（占用一个槽 slot）和 TABLE-DELETE（释放一个槽）；底层组织方式（栈、堆、散列表、数组）无关紧要。
• 装载因子（load factor）\(\alpha(T)\) = 表中项数 / 表大小（槽数）。空表大小记为 0，装载因子定义为 1。若装载因子有常数下界，浪费空间就不超过常数比例。

17.4.1 表扩张（Table expansion）

表存储为连续数组，满（装载因子为 1）时扩张：分配更大的新数组并把旧项复制过去（开放寻址散列表等可在装载因子达到某个小于 1 的常数时就视为满，见习题 17.4-1）。常用启发式：加倍。只插入时装载因子始终 ≥ 1/2，浪费空间不超过一半。

def TABLE_INSERT(T, x):
    if T.size == 0:
        T.table = allocate(1); T.size = 1
    if T.num == T.size:                       # 表满：扩张
        new_table = allocate(2 * T.size)
        copy all items of T.table into new_table   # 基本插入 T.num 次
        free(T.table)
        T.table = new_table
        T.size = 2 * T.size
    insert x into T.table                     # 一次基本插入
    T.num += 1

• 以"基本插入"（elementary insertion，第 6、10 行）为单位计代价，分配/释放开销被复制开销支配。执行第 5–9 行称为一次扩张（expansion）。
• 第 \(i\) 个操作：表有空位时 \(c_i=1\)；扩张时 \(c_i=i\)（1 次插入 + 复制 \(i-1\) 项）。粗略界 \(O(n^2)\) 不紧。

聚合分析。 仅当 \(i-1\) 为 2 的精确幂时扩张：

核算法直观。 每项付 3 美元：1 美元插入自己；1 美元存在自己身上，供下次扩张时搬移自己；1 美元存在表中已有的、已被搬过一次的某一项上，供其下次搬移。设扩张后表大小为 \(m\)，其中有 \(m/2\) 项且无信用；再插入 \(m/2\) 项填满时，每项都恰有 1 美元可用于重新插入。

势能法。 希望势能在扩张后为 0，到表满时增长到表大小：

• 不扩张：\(size_i=size_{i-1}\)，\(\hat c_i=1+(2num_i-size_i)-(2(num_i-1)-size_i)=3\)。
• 扩张：\(size_i=2size_{i-1}\)，\(size_{i-1}=num_{i-1}=num_i-1\)，于是 \(size_i=2(num_i-1)\)， \(\hat c_i=num_i+(2num_i-2(num_i-1))-(2(num_i-1)-(num_i-1))=num_i+2-(num_i-1)=3\)。
• 图 17.3：势能在每次扩张前积累到等于项数，恰好付清搬移代价；扩张后降为 0，随即因插入那一项升为 2。

17.4.2 表扩张与收缩（Table expansion and contraction）

希望同时保持：(1) 装载因子有正常数下界；(2) 每个操作摊还代价有常数上界。代价以基本插入和基本删除计。

错误策略：满时加倍、低于半满时减半。 装载因子虽 ≥ 1/2，但摊还代价可能很大。反例：\(n\) 为 2 的幂，前 \(n/2\) 次插入（共 \(\Theta(n)\)），此时 \(num=size=n/2\)；之后执行"插、删、删、插、插、删、删、插、插……"。第一次插入扩张到 \(n\)，两次删除又收缩回 \(n/2\)，再两次插入又扩张……每次扩张/收缩 \(\Theta(n)\)，共 \(\Theta(n)\) 次，总 \(\Theta(n^2)\)，摊还 \(\Theta(n)\)。原因：扩张后删除的项不足以支付收缩，收缩后插入的项不足以支付扩张（"抖动" thrashing）。

正确策略：满时加倍，删除后低于 1/4 满时减半。 装载因子下界为 1/4。直观上装载因子 1/2 最理想，势能为 0；偏离 1/2 时势能增长，到装载因子为 1 或 1/4 时势能达到 \(T.num\)，足以支付复制。扩张或收缩后装载因子回到 1/2，势能降回 0。约定项数降到 0 时释放存储，即 \(num=0\Rightarrow size=0\)。

由 \(\alpha(T)=T.num/T.size\)（空表时 \(\alpha=1\)），总有 \(T.num=\alpha(T)\cdot T.size\)。势函数

逐情形分析（初值 \(num_0=size_0=0,\alpha_0=1,\Phi_0=0\)）：

• TABLE-INSERT，\(\alpha_{i-1}\ge1/2\)：与 17.4.1 相同，无论是否扩张 \(\hat c_i\le3\)。
• TABLE-INSERT，\(\alpha_{i-1}<1/2\)：不可能扩张（只在 \(\alpha_{i-1}=1\) 时扩张）。
  • 若 \(\alpha_i<1/2\)：\(\hat c_i=1+(size_i/2-num_i)-(size_i/2-(num_i-1))=0\)。
  • 若 \(\alpha_i\ge1/2\)：\(\hat c_i=1+(2(num_{i-1}+1)-size_{i-1})-(size_{i-1}/2-num_{i-1})=3num_{i-1}-\tfrac32size_{i-1}+3=3\alpha_{i-1}size_{i-1}-\tfrac32size_{i-1}+3<\tfrac32size_{i-1}-\tfrac32size_{i-1}+3=3\)。
  • 故插入摊还 ≤ 3。
• TABLE-DELETE，\(\alpha_{i-1}<1/2\)（\(num_i=num_{i-1}-1\)）：
  • 不收缩：\(\hat c_i=1+(size_i/2-num_i)-(size_i/2-(num_i+1))=2\)。
  • 收缩：实际代价 \(c_i=num_i+1\)（删 1 项、搬 \(num_i\) 项），且 \(size_i/2=size_{i-1}/4=num_{i-1}=num_i+1\)， \(\hat c_i=(num_i+1)+((num_i+1)-num_i)-((2num_i+2)-(num_i+1))=1\)。
• TABLE-DELETE，\(\alpha_{i-1}\ge1/2\)：摊还代价也有常数上界（留作习题 17.4-2）。

结论：每个操作摊还代价有常数上界，任意 \(n\) 个操作的实际总时间 \(O(n)\)；空间利用率 ≥ 1/4。

习题 17.4 概括：17.4-1 动态开放寻址散列表为什么在装载因子到某个 \(\alpha<1\) 时就视为满，如何让每次插入的期望摊还代价为 \(O(1)\)，以及为何单次插入的期望实际代价不一定为 \(O(1)\)；17.4-2 补全 \(\alpha_{i-1}\ge1/2\) 时删除的分析；17.4-3 改为装载因子低于 1/3 时把大小乘 2/3，用 \(\Phi=|2\cdot T.num-T.size|\) 证明删除摊还代价有常数界。

第 17 章思考题（PDF p.493–498）

• 17-1 位反转二进制计数器：FFT 第一步的位反转置换（bit-reversal permutation），交换下标二进制表示互为反转的元素。\(\mathrm{rev}_k(a)=\sum_{i=0}^{k-1}a_{k-i-1}2^i\)，例 \(k=4\) 时 \(\mathrm{rev}_4(3)=12\)（0011→1100）。(a) 已知 \(\Theta(k)\) 的 \(\mathrm{rev}_k\)，给出 \(O(nk)\) 算法；(b) 字长 \(k\)、移位与按位运算单位时间时，实现 BIT-REVERSED-INCREMENT（产生 \(\mathrm{rev}_k(\mathrm{rev}_k(a)+1)\)，序列 0,8,4,12,2,10,…），使整体 \(O(n)\)；(c) 若只能每次移 1 位，能否仍为 \(O(n)\)。
• 17-2 让二分查找动态化：\(k=\lceil\lg(n+1)\rceil\) 个有序数组 \(A_0,\dots,A_{k-1}\)，\(|A_i|=2^i\)，按 \(n\) 的二进制位决定满或空。(a) SEARCH：逐个数组二分，最坏 \(O(\lg^2n)\)；(b) INSERT：类似二进制加 1，合并有序数组，最坏 \(\Theta(n)\)，摊还 \(O(\lg n)\)；(c) 讨论 DELETE。
• 17-3 摊还的权重平衡树：每个结点存子树大小 \(x.size\)；\(1/2\le\alpha<1\)，结点 \(\alpha\)-平衡指左右子树大小都 ≤ \(\alpha\cdot x.size\)。(a) \(\Theta(x.size)\) 时间把子树重建为 1/2-平衡；(b) \(\alpha\)-平衡树查找 \(O(\lg n)\)；插入/删除后若有结点失衡，重建最高的失衡结点的子树。势能 \(\Phi(T)=c\sum_{x:\Delta(x)\ge2}\Delta(x)\)，\(\Delta(x)=|x.left.size-x.right.size|\)。(c) 势能非负、1/2-平衡树势能为 0；(d) 求 \(c\) 关于 \(\alpha\) 的取值使重建摊还 \(O(1)\)；(e) 插入/删除摊还 \(O(\lg n)\)。
• 17-4 红黑树重构代价：结构修改包括结点插入、删除、旋转、改色。(a) 构造使 RB-INSERT 或 RB-DELETE 产生 \(\Omega(\lg n)\) 次改色的例子；(b) 区分 RB-INSERT-FIXUP、RB-DELETE-FIXUP 中的"终止"情形与非终止情形；(c)–(e) 只插入时以红结点数为势能，证明每次 RB-INSERT 摊还 \(O(1)\) 次结构修改；(f)–(h) 定义 \(w(x)\)：红结点 0、无红孩子的黑结点 1、一个红孩子的黑结点 0、两个红孩子的黑结点 2，\(\Phi=\sum w(x)\)，证明非终止情形使势能至少降 1，从而 \(m\) 次插入删除共 \(O(m)\) 次结构修改。
• 17-5 自组织表的竞争分析（move-to-front）：在链表中查找第 \(k\) 个元素代价 \(k\)，相邻交换（transpose）代价 1。(a) 不知道访问序列的启发式最坏代价 \(\Omega(mn)\)；(b) move-to-front（MTF，访问后移到表头）的代价 \(c_i=2\,\mathrm{rank}_L(x)-1\)；(c) 任意启发式 H 的代价 \(c_i^*=\mathrm{rank}_{L^*_{i-1}}(x)+t_i^*\)；以两表间逆序对数 \(q_i\) 定义势能 \(\Phi(L_i)=2q_i\)（例：\(L_i=\langle e,c,a,d,b\rangle\)，\(L_i^*=\langle c,a,b,d,e\rangle\)，5 个逆序对，\(\Phi=10\)）；(d) 一次交换使势能 ±2；(e)–(f) 把其他元素按在两表中位于 \(x\) 前后分成 A、B、C、D 四类，\(\mathrm{rank}_{L_{i-1}}(x)=|A|+|B|+1\)，\(\mathrm{rank}_{L^*_{i-1}}(x)=|A|+|C|+1\)，势能变化 \(\le2(|A|-|B|+t_i^*)\)；(g) \(\hat c_i\le4c_i^*\)；(h) MTF 代价至多为任何启发式（即使预知访问序列）的 4 倍。这类分析称为竞争分析（competitive analysis）。

本章注记（PDF p.499）：Aho–Hopcroft–Ullman 用聚合分析分析不相交集合森林（第 21 章将用势能法）；Tarjan 综述核算法与势能法；"amortized"一词由 Sleator 与 Tarjan 提出，势能法归功于 Sleator。势函数也可用于证明下界：步数 ≥ \(|\Phi_{final}-\Phi_{init}|/|\Delta\Phi_{max}|\)（用于 I/O 复杂度、gossiping 问题）。若可在常数时间把元素摘出并移到表头，MTF 的代价至多为任何启发式的 2 倍。

第 17 章本章要点

• 摊还分析给出的是最坏情况下的平均代价，不含概率。三种方法：聚合（总量/次数）、核算（按操作类型收费，信用存于对象，需保持非负）、势能（\(\hat c_i=c_i+\Delta\Phi\)，要求 \(\Phi(D_i)\ge\Phi(D_0)\)）。
• 经典结论：带 MULTIPOP 的栈、二进制计数器均摊还 \(O(1)\)；动态表"满则加倍、低于 1/4 则减半"使插入删除摊还 \(O(1)\)，且装载因子 ≥ 1/4；"低于 1/2 就减半"会抖动导致 \(\Theta(n)\) 摊还。
• 势函数设计原则：在昂贵操作即将发生时，势能恰好积累到足以支付它；昂贵操作之后势能清零。

与量化交易的关联

• 系统实现：动态数组（Python list、C++ std::vector、NumPy 追加时预分配）就是 17.4 的动态表。实时行情接收、逐笔成交缓冲区、订单簿价位数组都依赖"加倍扩容"的 \(O(1)\) 摊还插入。要注意摊还 ≠ 每次都快：扩容那一次是 \(\Theta(n)\) 的停顿，在低延迟交易系统中会形成延迟尖峰（latency spike），所以生产系统通常预先分配足够容量或使用环形缓冲区（ring buffer），把摊还界变成真正的最坏界。
• 收缩阈值 1/4 vs 1/2 的抖动例子，对应实盘中缓存/队列在阈值附近反复扩缩容导致性能抖动的问题，设计时要留滞后区间（hysteresis）。这一思想与交易信号中设置进出场不同阈值以避免频繁换仓是同一逻辑。
• 17-2（多层有序数组，类似 LSM-tree 的思想）是时序数据库（如 kdb+、ClickHouse、RocksDB）写优化存储的原型，适合理解行情库的写入/查询代价权衡。
• 竞争分析（17-5）是在线算法分析框架，与在线组合选择、执行算法中"与事后最优比较"的竞争比思路相通。

推荐习题

• 17.1-3 / 17.2-2 / 17.3-2（同一问题三种方法对照，最适合教学）。
• 17.3-6（两个栈实现队列，面试与工程常见）。
• 17.4-2、17.4-3（补全动态表的势能分析，掌握分段势函数）。
• 思考题 17-2（动态二分查找，LSM 思想），17-5（move-to-front 竞争比）。

第 V 部分 高级数据结构（Advanced Data Structures）导言（PDF p.500–504）

PDF p.500 为空白页，p.501 为部分标题页。本部分在第 III 部分基础上研究支持动态集合操作的更高级数据结构，其中两章大量使用第 17 章的摊还分析。

• 第 18 章 B 树：为磁盘设计的平衡搜索树，性能除计算时间外还看磁盘访问次数；访问次数随树高增长，B 树保持树高很低。
• 第 19 章 Fibonacci 堆：实现可合并堆（mergeable heap），支持 INSERT、MINIMUM、EXTRACT-MIN、UNION，以及 DELETE、DECREASE-KEY。INSERT、MINIMUM、UNION 实际与摊还时间均 \(O(1)\)；EXTRACT-MIN、DELETE 摊还 \(O(\lg n)\)；最大优势是 DECREASE-KEY 摊还 \(O(1)\)，因此是若干渐近最快图算法的关键组件。默认可合并堆指可合并最小堆。
• 第 20 章 van Emde Boas 树：关键字为 \(\{0,1,\dots,u-1\}\) 中互异整数（\(u\) 为 2 的幂）时，SEARCH、INSERT、DELETE、MINIMUM、MAXIMUM、SUCCESSOR、PREDECESSOR 均 \(O(\lg\lg u)\)，突破比较模型的 \(\Omega(\lg n)\)。
• 第 21 章不相交集合：UNION 合并两个集合，FIND-SET 查询元素所在集合；用有根树表示，\(m\) 个操作 \(O(m\,\alpha(n))\)，\(\alpha(n)\) 增长极慢，在任何可想象的应用中 ≤ 4；其摊还分析之复杂与结构之简单形成对比。

书中未涵盖的其他高级结构：

• 动态树（dynamic trees，Sleator–Tarjan）：维护不相交有根树森林，边有实数代价，支持找父亲、根、边代价、到根路径上最小边，及剪边、路径加值、连接、换根；摊还或最坏 \(O(\lg n)\)；用于最快的网络流算法。
• 伸展树（splay trees）：标准操作摊还 \(O(\lg n)\) 的 BST，可简化动态树。
• 持久化数据结构（persistent data structures）：可查询（有时可更新）历史版本（Driscoll 等；思考题 13-1）。
• 受限整数域上的更快字典：融合树（fusion trees，Fredman–Willard）\(O(\lg n/\lg\lg n)\)；指数搜索树等。
• 动态图数据结构：支持插入删除顶点/边的同时回答连通性、边连通性、最小生成树、双连通性、传递闭包等查询。

第 18 章 B 树（B-Trees）（PDF p.505–525）

18.0 导言与辅存上的数据结构（PDF p.505–509）

B 树（B-tree）是为磁盘等直接存取辅存设备设计的平衡搜索树。与红黑树相似（\(n\) 个结点高度 \(O(\lg n)\)），但更擅长减少磁盘 I/O；很多数据库系统用 B 树或其变体存储数据。

• 结点可有很多孩子（几个到几千个），分支因子（branching factor）大，因而对数的底大、实际高度远低于红黑树。
• 推广 BST：内部结点 \(x\) 含 \(x.n\) 个关键字，就有 \(x.n+1\) 个孩子；这些关键字把 \(x\) 负责的关键字区间分成 \(x.n+1\) 个子区间。查找时在 \(x\) 做 \((x.n+1)\) 路分支决定。
• 图 18.1：关键字为英文辅音字母的 B 树，根为 M，第二层为 D H 与 Q T X，叶子如 BC、FG、JKL、NP、RS、VW、YZ；查找 R 经过根 → QTX → RS。所有叶子在同一深度。

辅存。 主存（primary/main memory，硅芯片）每位成本比磁带/磁盘高一个数量级以上；辅存（secondary storage，磁盘）容量通常比主存大至少两个数量级。

• 磁盘结构（图 18.2）：多张盘片（platter）绕主轴（spindle）旋转，磁头（head）装在臂（arm）末端；磁头静止时扫过的环面叫磁道（track）。多盘片只增容量不增性能。
• 磁盘慢在机械运动：盘片旋转与臂移动。商用盘 5400–15000 RPM；7200 RPM 时转一圈 8.33 ms，比 50 ns 的内存访问长 5 个数量级以上（等一圈可访问内存 10 万次以上），平均等半圈；平均访问时间 8–11 ms。（原书注：当时固态硬盘刚进入消费市场，更快但每 GB 更贵、容量更小。）
• 为摊薄机械等待，磁盘按页（page）读写，每页常为 \(2^{11}\)–\(2^{14}\) 字节；定位后读写是电子过程，很快。读取一页往往比检查读到的所有信息更耗时，因此分开考虑两种代价：磁盘访问次数（以读写的页数衡量，作为一阶近似）与 CPU 时间。

磁盘操作的伪代码模型。 对象在磁盘上时须先 DISK-READ(x) 读入主存才能访问属性（已在主存则为空操作）；修改后用 DISK-WRITE(x) 写回。典型模式：

x = 指向某对象的指针
DISK-READ(x)
访问/修改 x 的属性
DISK-WRITE(x)        # 若未修改则省略
其他只读访问 x 的操作

• B 树算法任一时刻只在主存中保留常数个页，所以主存大小不限制可处理的 B 树大小；系统负责把不用的页刷出。
• 一个 B 树结点通常与一个磁盘页一样大，页大小限制了孩子数。大型磁盘 B 树的分支因子常为 50–2000（取决于关键字相对页的大小）。
• 图 18.3：分支因子 1001（每个结点 1000 个关键字）、高度 2 的 B 树：根 1 个结点 1000 个关键字；深度 1 有 1001 个结点共 1,001,000 个关键字；深度 2 有 1,002,001 个结点共 1,002,001,000 个关键字，即超过 10 亿个关键字。根常驻内存，找任何关键字至多 2 次磁盘访问。

18.1 B 树的定义（Definition of B-trees）（PDF p.509–512）

约定：与关键字关联的卫星数据（satellite information）与关键字存在同一结点（实践中可只存指向卫星数据页的指针），移动关键字时卫星数据随之移动。常见变体 B+ 树（B+-tree）：卫星数据全部存在叶子，内部结点只存关键字和孩子指针，以最大化内部结点的分支因子。

定义。 B 树 \(T\) 是有根树（根为 \(T.root\)），满足：

1. 每个结点 \(x\) 有属性：\(x.n\)（当前关键字数）；\(x.n\) 个关键字按非降序存放 \(x.key_1\le x.key_2\le\cdots\le x.key_{x.n}\)；布尔值 \(x.leaf\)（是否叶子）。
2. 每个内部结点有 \(x.n+1\) 个孩子指针 \(x.c_1,\dots,x.c_{x.n+1}\)；叶子的 \(c_i\) 无定义。
3. 关键字分隔各子树的关键字范围：若 \(k_i\) 是以 \(x.c_i\) 为根的子树中任一关键字，则
   \[k_1\le x.key_1\le k_2\le x.key_2\le\cdots\le x.key_{x.n}\le k_{x.n+1}.\]
4. 所有叶子深度相同，即树高 \(h\)。
5. 结点关键字数有上下界，用固定整数 \(t\ge2\)（最小度数 minimum degree）表示：
   • (a) 除根以外每个结点至少 \(t-1\) 个关键字，因此除根外的内部结点至少 \(t\) 个孩子；树非空时根至少 1 个关键字。
   • (b) 每个结点至多 \(2t-1\) 个关键字，内部结点至多 \(2t\) 个孩子。恰有 \(2t-1\) 个关键字的结点称为满的（full）。
   • 另一常见变体 B* 树要求每个内部结点至少 2/3 满（B 树只要求半满）。

\(t=2\) 是最简单的 B 树：内部结点有 2、3 或 4 个孩子，即 2-3-4 树。实践中 \(t\) 大得多，树更矮。

B 树的高度。

定理 18.1：若 \(n\ge1\)，任意含 \(n\) 个关键字、高 \(h\)、最小度数 \(t\ge2\) 的 B 树满足

意义：B 树与红黑树高度都是 \(O(\lg n)\)（\(t\) 为常数），但 B 树对数的底大得多，查访结点数约节省 \(\lg t\) 倍，从而大幅减少磁盘访问。

习题 18.1 概括：18.1-1 为什么不允许 \(t=1\)（非根结点可以没有关键字，失去意义）；18.1-2 图 18.1 的树在哪些 \(t\) 值下合法；18.1-3 画出表示 {1,2,3,4,5} 的所有最小度数 2 的合法 B 树；18.1-4 高为 \(h\) 的 B 树最多存 \((2t)^{h+1}-1\) 个关键字；18.1-5 红黑树中每个黑结点吸收其红孩子后得到什么结构（2-3-4 树）。

18.2 B 树的基本操作（Basic operations on B-trees）（PDF p.512–520）

两条约定：(1) 根结点始终在主存，不需对根 DISK-READ，但根改变时要 DISK-WRITE；(2) 作为参数传入的结点都已 DISK-READ 过。所有过程都是从根向下的单程（one-pass）算法，不回溯。

查找 B-TREE-SEARCH。 在每个内部结点做 \((x.n+1)\) 路分支，是 TREE-SEARCH 的直接推广。顶层调用 B-TREE-SEARCH(T.root, k)，找到返回有序对 \((y,i)\) 使 \(y.key_i=k\)，否则返回 NIL。

def B_TREE_SEARCH(x, k):
    i = 1
    while i <= x.n and k > x.key[i]:      # 线性查找第一个 >= k 的关键字
        i += 1
    if i <= x.n and k == x.key[i]:
        return (x, i)
    elif x.leaf:
        return None
    else:
        DISK_READ(x.c[i])
        return B_TREE_SEARCH(x.c[i], k)

• 复杂度：访问 \(O(h)=O(\log_t n)\) 个磁盘页；每个结点 while 循环 \(O(t)\)（\(x.n<2t\)），CPU 总时间 \(O(th)=O(t\log_t n)\)。（习题 18.2-6：结点内改用二分查找，CPU 时间变为 \(O(\lg n)\)，与 \(t\) 无关。）

创建空树 B-TREE-CREATE。 借助 ALLOCATE-NODE（\(O(1)\) 时间分配一个磁盘页，新结点无需 DISK-READ）。

def B_TREE_CREATE(T):
    x = ALLOCATE_NODE()
    x.leaf = True; x.n = 0
    DISK_WRITE(x)
    T.root = x

\(O(1)\) 次磁盘操作、\(O(1)\) CPU 时间。

插入的思路。 比 BST 复杂：不能新建叶子（会破坏"叶子等深"），而是把关键字插入已有的叶子。叶子满了不能插，所以引入分裂（split）：把满结点 \(y\)（\(2t-1\) 个关键字）按中位关键字 \(y.key_t\) 分成两个各含 \(t-1\) 个关键字的结点，中位关键字上移到父结点作为分界。若父结点也满，则需先分裂父结点，可能一路分裂到根。

• 单程插入的技巧：沿树下行寻找插入位置时，遇到满结点就预先分裂（包括叶子本身），从而保证每当要分裂结点 \(y\) 时，它的父结点一定不满。

分裂 B-TREE-SPLIT-CHILD(x, i)。 输入：非满的内部结点 \(x\)（在主存）与下标 \(i\)，\(x.c_i\) 是 \(x\) 的满孩子（也在主存）。把该孩子一分为二，\(x\) 多一个孩子。分裂满根时，先让根成为一个新的空根的孩子再调用本过程——树高因此加一，分裂是树长高的唯一途径。图 18.5（\(t=4\)）：\(y=x.c_i\) 含 P Q R S T U V，中位 S 上移到 \(x\)（位于 N 与 W 之间），T U V 移到新结点 \(z=x.c_{i+1}\)。

def B_TREE_SPLIT_CHILD(x, i):
    z = ALLOCATE_NODE()
    y = x.c[i]
    z.leaf = y.leaf
    z.n = t - 1
    for j in range(1, t):              # z 取 y 的后 t-1 个关键字
        z.key[j] = y.key[j + t]
    if not y.leaf:
        for j in range(1, t + 1):      # 以及后 t 个孩子
            z.c[j] = y.c[j + t]
    y.n = t - 1
    for j in range(x.n + 1, i, -1):    # x 中孩子指针右移，腾出位置给 z
        x.c[j + 1] = x.c[j]
    x.c[i + 1] = z
    for j in range(x.n, i - 1, -1):    # x 中关键字右移
        x.key[j + 1] = x.key[j]
    x.key[i] = y.key[t]                # 中位关键字上移
    x.n += 1
    DISK_WRITE(y); DISK_WRITE(z); DISK_WRITE(x)

• \(y\) 原有 \(2t\) 个孩子（\(2t-1\) 个关键字），分裂后剩 \(t\) 个孩子（\(t-1\) 个关键字）；\(z\) 取走最大的 \(t\) 个孩子（\(t-1\) 个关键字），成为 \(x\) 中紧随 \(y\) 之后的孩子。
• 复杂度：CPU \(\Theta(t)\)，\(O(1)\) 次磁盘操作。

单程插入 B-TREE-INSERT。

def B_TREE_INSERT(T, k):
    r = T.root
    if r.n == 2 * t - 1:               # 根满：先分裂根，树高 +1
        s = ALLOCATE_NODE()
        T.root = s
        s.leaf = False; s.n = 0
        s.c[1] = r
        B_TREE_SPLIT_CHILD(s, 1)
        B_TREE_INSERT_NONFULL(s, k)
    else:
        B_TREE_INSERT_NONFULL(r, k)

def B_TREE_INSERT_NONFULL(x, k):       # 前提：x 不满
    i = x.n
    if x.leaf:
        while i >= 1 and k < x.key[i]: # 在叶子中插入排序式右移
            x.key[i + 1] = x.key[i]
            i -= 1
        x.key[i + 1] = k
        x.n += 1
        DISK_WRITE(x)
    else:
        while i >= 1 and k < x.key[i]:
            i -= 1
        i += 1                          # 应下降到孩子 c[i]
        DISK_READ(x.c[i])
        if x.c[i].n == 2 * t - 1:       # 孩子满则先分裂
            B_TREE_SPLIT_CHILD(x, i)
            if k > x.key[i]:            # 判断该走分裂后的哪一半
                i += 1
        B_TREE_INSERT_NONFULL(x.c[i], k)

• 与 BST 不同，B 树在顶部长高（图 18.6，\(t=4\)：满根 A D F H L N P 分裂，H 成为新根 \(s\) 的唯一关键字）。
• 第 16 行 \(i\) 加 1 后无须再 DISK-READ，因为下降到的是刚由分裂创建、仍在主存的结点。
• 复杂度：\(O(h)\) 次磁盘访问（两次递归调用之间只有 \(O(1)\) 次读写），CPU \(O(th)=O(t\log_t n)\)。B-TREE-INSERT-NONFULL 是尾递归，可改写为 while 循环，因此任一时刻主存只需 \(O(1)\) 个页。

插入例子（图 18.7，\(t=3\)，结点至多 5 个关键字）：初始根 G M P X，叶子 A C D E / J K / N O / R S T U V / Y Z。

• (b) 插入 B：简单插入叶子，得 A B C D E。
• (c) 插入 Q：叶子 R S T U V 已满，分裂为 R S 与 U V，T 上移到根（根变 G M P T X），Q 插入 R S 得 Q R S。
• (d) 插入 L：根 G M P T X 已满，立即分裂，P 成为新根，树高加一（左孩子 G M，右孩子 T X）；L 插入 J K 得 J K L。
• (e) 插入 F：叶子 A B C D E 满，先分裂（C 上移，得 C G M），F 插入右半 D E 得 D E F。

习题 18.2 概括：18.2-1 把 F,S,Q,K,C,L,H,T,V,W,M,R,N,P,A,B,X,Y,D,Z,E 依次插入 \(t=2\) 的空 B 树并画分裂前与最终形态；18.2-2 何时会出现冗余的 DISK-READ/DISK-WRITE；18.2-3 如何找最小关键字和前驱；18.2-4（星号）按 1..n 顺序插入 \(t=2\) 的 B 树最终有多少结点；18.2-5 叶子不需孩子指针，可用更大的 \(t\)，修改创建与插入过程；18.2-6 结点内二分查找使 CPU 时间为 \(O(\lg n)\)；18.2-7 读页时间为 \(a+bt\) 时如何选 \(t\) 最小化查找时间（\(a=5\) ms，\(b=10\,\mu\)s 时求最优 \(t\)——最小化 \((a+bt)\log_t n\propto(a+bt)/\ln t\)）。

18.3 从 B 树中删除关键字（Deleting a key from a B-tree）（PDF p.520–523）

删除比插入稍复杂：可从任意结点（不只叶子）删除；从内部结点删除时要重排孩子。需防止结点过小（根除外，根允许少于 \(t-1\) 个关键字）。

核心设计：B-TREE-DELETE(x, k) 保证每次递归调用到结点 \(x\) 时，\(x\) 至少有 \(t\) 个关键字——比最低要求多 1 个。因此有时要先把一个关键字移入孩子，再下降。这使删除能在一次下行中完成，几乎不必回溯（唯一例外见 2a/2b）。若根结点 \(x\) 变成没有关键字的内部结点（情形 2c、3b 可能发生），删除 \(x\)，其唯一孩子 \(x.c_1\) 成为新根，树高减一。

书中只给出过程描述（图 18.8，\(t=3\)，非根结点至少 2 个关键字）：

1. 情形 1：\(k\) 在结点 \(x\) 中且 \(x\) 是叶子 → 直接从 \(x\) 删除 \(k\)。（例：删除 F。）
2. 情形 2：\(k\) 在内部结点 \(x\) 中：
   • 2a：若 \(x\) 中位于 \(k\) 前面的孩子 \(y\) 至少有 \(t\) 个关键字，在以 \(y\) 为根的子树中找 \(k\) 的前驱 \(k'\)，递归删除 \(k'\)，并在 \(x\) 中用 \(k'\) 替换 \(k\)（找与删可在一次下行中完成）。（例：删除 M，前驱 L 上移取代 M。）
   • 2b：否则对称地考察 \(k\) 后面的孩子 \(z\)；若 \(z\) 至少有 \(t\) 个关键字，用后继 \(k'\) 替换 \(k\) 并递归删除 \(k'\)。
   • 2c：若 \(y\)、\(z\) 都只有 \(t-1\) 个关键字，把 \(k\) 和 \(z\) 的全部内容合并进 \(y\)，\(x\) 失去 \(k\) 和指向 \(z\) 的指针，\(y\) 现在有 \(2t-1\) 个关键字；释放 \(z\)，再从 \(y\) 中递归删除 \(k\)。（例：删除 G，把 G 下推形成 D E G J K，再按情形 1 删 G。）
3. 情形 3：\(k\) 不在内部结点 \(x\) 中：确定必然包含 \(k\) 的子树根 \(x.c_i\)。若 \(x.c_i\) 只有 \(t-1\) 个关键字，先执行 3a 或 3b 保证下降到的结点至少有 \(t\) 个关键字，然后对合适的孩子递归。
   • 3a：\(x.c_i\) 只有 \(t-1\) 个关键字，但有一个相邻兄弟至少 \(t\) 个 → 从 \(x\) 下移一个关键字到 \(x.c_i\)，从该兄弟上移一个关键字到 \(x\)，并把相应的孩子指针从兄弟移到 \(x.c_i\)（相当于"旋转/借位"）。（例：删除 B，C 下移填 B 的位置，E 上移填 C 的位置。）
   • 3b：\(x.c_i\) 及其所有相邻兄弟都只有 \(t-1\) 个关键字 → 把 \(x.c_i\) 与一个兄弟合并，从 \(x\) 下移一个关键字作为合并结点的中位关键字。（例：删除 D，递归无法下降到只有 2 个关键字的 C L，于是把 P 下推，与 C L、T X 合并为 C L P T X，然后从叶子删 D；根变空，被删除，树高减一。）

复杂度：大部分关键字在叶子中，实践中删除多发生在叶子，此时一次下行完成；从内部结点删除时，可能需要返回到删除关键字的结点用前驱/后继替换（2a、2b）。总之高 \(h\) 的 B 树删除只需 \(O(h)\) 次磁盘操作（递归调用之间 \(O(1)\) 次读写），CPU 时间 \(O(th)=O(t\log_t n)\)。

习题 18.3 概括：18.3-1 从图 18.8(f) 的树依次删除 C、P、V；18.3-2 写出 B-TREE-DELETE 伪代码。

第 18 章思考题（PDF p.523–525）

• 18-1 辅存上的栈：每页 \(m\) 个字。(a) 整个栈放磁盘，栈指针 \(p\) 指向第 \(\lfloor p/m\rfloor\) 页的第 \((p\bmod m)\) 个字：\(n\) 个操作最坏 \(O(n)\) 次磁盘访问、CPU \(O(nm)\)；(b)(c) 内存中保留一页：\(n\) 次 PUSH 只需 \(O(n/m)\) 次访问，但一般操作序列在页边界来回振荡时最坏 \(\Theta(n)\) 次；(d) 内存保留两页，设计管理策略使每个操作摊还磁盘访问 \(O(1/m)\)、摊还 CPU \(O(1)\)。
• 18-2 2-3-4 树的连接与分裂：join 操作（\(S'\) 中关键字均小于 \(x\)，\(S''\) 中均大于 \(x\)，返回 \(S'\cup\{x\}\cup S''\)）与 split 操作（其逆）。(a) 在每个结点维护子树高度 \(x.height\) 而不影响渐近时间；(b) \(O(1+|h'-h''|)\) 时间实现 join；(c) 根到 \(k\) 的路径把小于 \(k\) 的关键字分解成一串树 \(T'_0,\dots,T'_m\) 与分隔关键字 \(k'_1,\dots,k'_m\)，分析相邻树的高度关系；(d) 用 join 拼装，\(O(\lg n)\) 实现 split（连接代价望远镜相消）。

本章注记（PDF p.525）：Knuth、Aho–Hopcroft–Ullman、Sedgewick 讨论平衡树与 B 树，Comer 有全面综述；Guibas–Sedgewick 讨论红黑树、2-3-4 树等的关系；Hopcroft 1970 发明 2-3 树（B 树前身）；Bayer 与 McCreight 1972 提出 B 树（未解释命名）；Bender–Demaine–Farach-Colton 研究缓存无关（cache-oblivious）B 树，在不知道存储层次传输块大小时也能高效。

第 18 章本章要点

• B 树为外存设计：结点 = 一个磁盘页，分支因子大（最小度数 \(t\)，每结点 \(t-1\) 到 \(2t-1\) 个关键字），所有叶子等深，高度 \(h\le\log_t\frac{n+1}{2}\)。
• 衡量代价用两项：磁盘访问 \(O(h)=O(\log_t n)\)，CPU 时间 \(O(t\log_t n)\)。
• 插入：遇满结点先按中位关键字分裂，单程下行；树只在根分裂时长高。删除：保证下降到的结点至少有 \(t\) 个关键字（借位 3a、合并 2c/3b），前驱/后继替换处理内部结点；树只在根变空时变矮。
• 变体：B+ 树（数据只在叶子）、B* 树（至少 2/3 满）、2-3-4 树（\(t=2\)，与红黑树等价）。

与量化交易的关联

• 系统实现/数据存储：几乎所有关系数据库（MySQL InnoDB、PostgreSQL）、文件系统和很多键值库的索引都是 B+ 树。在量化研究中，把行情、财务数据放进数据库时，"按 (代码, 日期) 建联合索引"的效率、范围查询（某股票一段时间的 K 线）快的原因、随机写入慢的原因，都可以用 B+ 树的结构解释：B+ 树叶子按键顺序链接，范围扫描只需一次定位加顺序读。
• 18.2-7 的页大小选择、18-1 的外存栈，体现"减少 I/O 次数而非 CPU 运算"的设计思想，这对处理 TB 级逐笔数据（列式存储 Parquet 的行组/页大小、kdb+ 的分区设计）同样适用。
• 订单簿的价格档位在内存中常用平衡树（红黑树 std::map）或 B 树变体（如 absl::btree_map）实现，后者因缓存友好在 CPU 缓存层面复现了 B 树的优势。
• 与因子研究、定价等数学建模环节没有直接关联。

推荐习题

• 18.1-4（高度为 \(h\) 时的最大关键字数）、18.1-5（红黑树 ↔ 2-3-4 树）。
• 18.2-1（手动插入，熟悉分裂）、18.2-3（最小值与前驱）、18.2-6（结点内二分查找）、18.2-7（页大小优化，工程味浓）。
• 18.3-2（写出完整的删除伪代码，是检验理解的最好练习）。
• 思考题 18-1（外存栈的摊还 I/O）。

第 19 章 斐波那契堆（Fibonacci Heaps）（PDF p.526–551）

19.0 导言（PDF p.526–528）

斐波那契堆有双重用途：一是支持"可合并堆"操作集；二是若干操作摊还时间为常数，适合频繁调用这些操作的应用。

可合并堆（mergeable heap）支持五个操作（每个元素有关键字）：

• MAKE-HEAP()：创建空堆；
• INSERT(H, x)：插入关键字已填好的元素 \(x\)；
• MINIMUM(H)：返回关键字最小元素的指针；
• EXTRACT-MIN(H)：删除并返回关键字最小的元素；
• UNION(H1, H2)：返回包含 \(H_1,H_2\) 所有元素的新堆，原堆被"销毁"。

斐波那契堆还支持：DECREASE-KEY(H, x, k)（把 \(x\) 的关键字改为不大于当前值的 \(k\)）与 DELETE(H, x)。默认是可合并最小堆；也可定义带 MAXIMUM、EXTRACT-MAX、INCREASE-KEY 的最大堆版本。

图 19.1 运行时间对比（\(n\) 为操作时堆中元素数）：

• 不需要 UNION 时二叉堆表现不错；需要 UNION 时二叉堆只能拼接数组再 BUILD-MIN-HEAP，最坏 \(\Theta(n)\)。
• 注意斐波那契堆的界是摊还界而非单次最坏界。

理论与实践。 理论上，当 EXTRACT-MIN 和 DELETE 次数相对其他操作较少时，斐波那契堆特别有利。例如一些图算法对每条边调用一次 DECREASE-KEY，在稠密图上 \(\Theta(1)\) 摊还对比二叉堆的 \(\Theta(\lg n)\) 是大改进；最小生成树（第 23 章）和单源最短路（第 24 章）的快速算法都依赖它。实践中，常数因子和编程复杂度使它通常不如二叉堆或 \(k\) 叉堆，除了某些管理大量数据的应用；它主要具有理论意义。

• 二叉堆和斐波那契堆都不擅长 SEARCH，所以 DECREASE-KEY、DELETE 需要以指向元素的指针为输入；应用中常在堆元素与应用对象之间互存句柄（handle）。
• 斐波那契堆基于有根树，每个元素是树中的一个结点，有 key 属性；本章用"结点"代替"元素"，并忽略结点的分配与释放。

19.1 斐波那契堆的结构（Structure of Fibonacci heaps）（PDF p.528–530）

定义。 斐波那契堆是一组最小堆有序（min-heap ordered）的有根树：每个结点的关键字 ≥ 其父结点的关键字。

结点表示（图 19.2）：

• x.p 指向父结点；x.child 指向任意一个孩子；
• \(x\) 的孩子们用环形双向链表（circular, doubly linked list）连起来，称为 \(x\) 的孩子表（child list）；每个孩子 \(y\) 有 y.left、y.right 指向左右兄弟，独生子时 y.left = y.right = y；兄弟顺序任意。
• 环形双向链表的两个好处：\(O(1)\) 时间在任意位置插入或删除结点；\(O(1)\) 时间把两个这样的链表拼接（splice）成一个。
• x.degree：孩子表中孩子个数；
• x.mark：布尔值，表示 \(x\) 自上次成为另一结点的孩子以来是否失去过孩子。新建结点不带标记；结点成为另一结点的孩子时清除标记。在 19.3 节之前所有 mark 都为 FALSE。
• 通过 H.min 访问堆：指向关键字最小的树根（最小结点 minimum node；若有多个最小根任取其一）；空堆时 H.min = NIL。
• 所有树根用 left/right 指针连成环形双向链表，称为根表（root list），树在根表中顺序任意。
• H.n：当前结点数。
• 图 19.2 例子：5 棵树、14 个结点，最小结点关键字 3，有 3 个被标记的结点（黑色）。

势函数。 记 \(t(H)\) 为根表中树的数目，\(m(H)\) 为被标记结点数：

最大度数。 假设已知 \(n\) 结点斐波那契堆中任意结点度数的上界 \(D(n)\)。只支持可合并堆操作时 \(D(n)\le\lfloor\lg n\rfloor\)（思考题 19-2(d)）；19.3–19.4 节证明支持 DECREASE-KEY 与 DELETE 时 \(D(n)=O(\lg n)\)。

19.2 可合并堆操作（Mergeable-heap operations）（PDF p.531–539）

核心理念：尽可能推迟工作（lazy）。插入只是把结点加到根表，\(O(1)\)；代价是若先插入 \(k\) 个结点再 EXTRACT-MIN，删除最小结点后要扫描其余 \(k-1\) 个根才能找到新最小值。既然 EXTRACT-MIN 无论如何要扫描整个根表，就顺便把结点合并（consolidate）成最小堆有序树来缩短根表。之后根表中每个结点的度数互不相同，根表大小至多 \(D(n)+1\)。

创建：MAKE-FIB-HEAP 返回 H.n = 0、H.min = NIL 的对象。\(t(H)=m(H)=0\)，势能 0，摊还代价 = 实际代价 \(O(1)\)。

插入：

def FIB_HEAP_INSERT(H, x):       # x 已分配且 x.key 已填
    x.degree = 0; x.p = None; x.child = None; x.mark = False
    if H.min is None:
        create a root list for H containing just x
        H.min = x
    else:
        insert x into H's root list
        if x.key < H.min.key:
            H.min = x
    H.n += 1

图 19.3：在图 19.2 的堆中插入关键字 21，它自成一棵树，成为根 3 的左兄弟。摊还分析：\(t(H')=t(H)+1\)，\(m(H')=m(H)\)，势能增 1，摊还代价 \(O(1)+1=O(1)\)。

求最小：直接返回 H.min，\(O(1)\)，势能不变。

合并：

def FIB_HEAP_UNION(H1, H2):
    H = MAKE_FIB_HEAP()
    H.min = H1.min
    concatenate the root list of H2 with the root list of H
    if H1.min is None or (H2.min is not None and H2.min.key < H1.min.key):
        H.min = H2.min
    H.n = H1.n + H2.n
    return H

所有根仍为根。\(t(H)=t(H_1)+t(H_2)\)，\(m(H)=m(H_1)+m(H_2)\)，势能变化为 0，摊还 = 实际 \(O(1)\)。

抽取最小结点——推迟的合并工作在这里完成。约定从链表删除结点时更新链表中剩余指针，但被删结点自身的指针不变。

def FIB_HEAP_EXTRACT_MIN(H):
    z = H.min
    if z is not None:
        for each child x of z:
            add x to the root list of H
            x.p = None
        remove z from the root list of H
        if z == z.right:          # z 是唯一的根且无孩子
            H.min = None
        else:
            H.min = z.right       # 暂指向任一其他根，不一定是新最小值
            CONSOLIDATE(H)
        H.n -= 1
    return z

合并根表：反复执行直到根表中各根度数互不相同——(1) 找两个度数相同的根 \(x,y\)，不妨 \(x.key\le y.key\)；(2) 把 \(y\) 链接（link）到 \(x\)：从根表删除 \(y\)，令其成为 \(x\) 的孩子（FIB-HEAP-LINK，\(x.degree\) 加 1 并清除 \(y\) 的标记）。

用辅助数组 \(A[0..D(H.n)]\) 按度数记录根：\(A[i]=y\) 表示 \(y\) 是当前度数为 \(i\) 的根。

def CONSOLIDATE(H):
    A = [None] * (D(H.n) + 1)
    for w in root list of H:
        x = w
        d = x.degree
        while A[d] is not None:          # 循环不变式：d == x.degree
            y = A[d]                     # 与 x 同度数的另一个根
            if x.key > y.key:
                x, y = y, x              # 保证 x 关键字较小，x 仍为根
            FIB_HEAP_LINK(H, y, x)
            A[d] = None
            d += 1
        A[d] = x
    H.min = None
    for i in range(D(H.n) + 1):          # 用 A 重建根表并找新最小值
        if A[i] is not None:
            if H.min is None:
                create a root list for H containing just A[i]
                H.min = A[i]
            else:
                insert A[i] into H's root list
                if A[i].key < H.min.key:
                    H.min = A[i]

def FIB_HEAP_LINK(H, y, x):
    remove y from the root list of H
    make y a child of x, incrementing x.degree
    y.mark = False

• while 循环不变式"每次迭代开始时 \(d=x.degree\)"：初始化由第 6 行保证；保持——\(A[d]\) 指向某根 \(y\)，\(x.degree=y.degree=d\)，关键字小者成为父亲，链接后 \(x.degree\) 加 1、\(y\) 不再是根，置 \(A[d]=\) NIL，\(d\) 加 1 恢复不变式；终止于 \(A[d]=\) NIL，即无其他同度数根。
• 例（图 19.4）：从根 3 被抽取开始（它的孩子 18、52、38 进入根表），依次处理根表：链接 23 到 7、17 到 7、24 到 7（得度数 3 的树根 7）；之后 21 与 52 链接、再与 18 链接，38 与 41 链接……最终根表为 7、18、38 三棵树，H.min 指向 7。

摊还分析。 设 \(H\) 为操作前的堆。

• 实际代价：处理至多 \(D(n)\) 个孩子和 CONSOLIDATE 第 2–3、16–23 行贡献 \(O(D(n))\)；for 循环用聚合分析：调用 CONSOLIDATE 时根表大小至多 \(D(n)+t(H)-1\)（原 \(t(H)\) 个根减去被抽取的根，加上至多 \(D(n)\) 个孩子）；每次 while 迭代把一个根链接到另一个根下，总迭代次数不超过根数。故实际代价 \(O(D(n)+t(H))\)。
• 势能：之前 \(t(H)+2m(H)\)，之后至多 \((D(n)+1)+2m(H)\)（至多 \(D(n)+1\) 个根，操作中不会有新标记）。
• 摊还代价 ≤ \(O(D(n)+t(H))+(D(n)+1+2m(H))-(t(H)+2m(H))=O(D(n))+O(t(H))-t(H)=O(D(n))\)（放大势能单位使其支配 \(O(t(H))\) 中的常数）。
• 直观：每次链接的代价由"根数减 1"带来的势能下降支付。19.4 节将证 \(D(n)=O(\lg n)\)，故 EXTRACT-MIN 摊还 \(O(\lg n)\)。

习题 19.2-1：对图 19.4(m) 的堆再执行一次 EXTRACT-MIN。

19.3 减小关键字与删除结点（Decreasing a key and deleting a node）（PDF p.539–543）

DECREASE-KEY（摊还 \(O(1)\)）：

def FIB_HEAP_DECREASE_KEY(H, x, k):
    if k > x.key:
        raise Error("new key is greater than current key")
    x.key = k
    y = x.p
    if y is not None and x.key < y.key:   # 违反最小堆序才需结构调整
        CUT(H, x, y)
        CASCADING_CUT(H, y)
    if x.key < H.min.key:
        H.min = x

def CUT(H, x, y):
    remove x from the child list of y, decrementing y.degree
    add x to the root list of H
    x.p = None
    x.mark = False

def CASCADING_CUT(H, y):
    z = y.p
    if z is not None:
        if y.mark == False:
            y.mark = True                 # 第一次失去孩子：仅标记
        else:
            CUT(H, y, z)                  # 第二次失去孩子：切下自己
            CASCADING_CUT(H, z)           # 向上级联

• 若 \(x\) 是根或 \(x.key\ge y.key\)，最小堆序未被破坏，无需结构变化。否则把 \(x\) 与父亲 \(y\) 的链接剪断，\(x\) 成为根。
• 标记的含义：记录结点的一小段历史。设结点 \(x\) 依次经历：(1) 某时刻是根；(2) 然后被链接为另一结点的孩子；(3) 然后有两个孩子被剪掉。一旦失去第二个孩子，就把 \(x\) 从父亲处剪下成为新根。x.mark = TRUE 表示 (1)(2) 已发生且已失去一个孩子。CUT 执行了步骤 (1)，所以清除标记；FIB-HEAP-LINK 执行了步骤 (2)，所以也清除被链接结点的标记。
• 级联切断（cascading cut）：\(x\) 可能是 \(y\) 自被链接以来失去的第二个孩子，所以对 \(y\) 调用 CASCADING-CUT：\(y\) 是根则直接返回；未标记则标记后返回；已标记则剪下 \(y\) 并对其父亲递归。递归向上直到遇到根或未标记结点。
• 新最小结点要么是原最小结点，要么是 \(x\)。
• 例（图 19.5）：(b) 把 46 减为 15：成为根，其父 24（原未标记）被标记，无级联。(c)–(e) 把 35 减为 5：5 成为根；其父 26 已标记 → 26 被切下成为未标记的根；26 的父 24 也已标记 → 24 被切下成为根；24 的父 7 是根，级联停止（即使 7 不是根，它未标记也会停止）。H.min 指向 5。

摊还分析。 设一次 DECREASE-KEY 导致 \(c\) 次 CASCADING-CUT 调用（第 7 行的 1 次加 \(c-1\) 次递归），每次不计递归为 \(O(1)\)，实际代价 \(O(c)\)。

• 势能变化：第 6 行的 CUT 生成以 \(x\) 为根的新树并清除 \(x\) 的标记；除最后一次外每次 CASCADING-CUT 都剪下一个已标记结点并清除标记。之后树的数目为 \(t(H)+c\)（原有树 + \(c-1\) 棵级联切出的树 + 以 \(x\) 为根的树），被标记结点至多 \(m(H)-c+2\)（\(c-1\) 个被清除标记，最后一次调用可能标记一个结点）。
  \[\Delta\Phi\le\big((t(H)+c)+2(m(H)-c+2)\big)-\big(t(H)+2m(H)\big)=4-c.\]
• 摊还代价 ≤ \(O(c)+4-c=O(1)\)（放大势能单位）。
• 为什么标记结点的系数是 2：级联切断剪下标记结点 \(y\) 时，清除标记使势能降 2；1 个单位支付剪切和清除标记，另 1 个单位抵消 \(y\) 成为新根带来的势能增加 1。

DELETE（摊还 \(O(D(n))=O(\lg n)\)）：假设堆中当前没有关键字 \(-\infty\)。

def FIB_HEAP_DELETE(H, x):
    FIB_HEAP_DECREASE_KEY(H, x, float('-inf'))   # 让 x 成为唯一最小结点
    FIB_HEAP_EXTRACT_MIN(H)

摊还代价 = \(O(1)+O(D(n))\)。

习题 19.3 概括：19.3-1 解释为何会出现被标记的根（标记后其父被切或被抽取，孩子变根时标记未清），并说明这不影响分析；19.3-2 用聚合分析说明 DECREASE-KEY 的 \(O(1)\) 平均代价。

19.4 最大度数的界（Bounding the maximum degree）（PDF p.544–547）

目标：证明 \(D(n)\le\lfloor\log_\phi n\rfloor\)，其中黄金分割率 \(\phi=(1+\sqrt5)/2=1.61803\ldots\)。关键：对任意结点 \(x\)（不必是根），定义 \(\mathrm{size}(x)\) 为以 \(x\) 为根的子树结点数（含 \(x\)），证明 \(\mathrm{size}(x)\) 关于 \(x.degree\) 呈指数增长（\(x.degree\) 始终准确维护）。

引理 19.1：设 \(x.degree=k\)，\(y_1,\dots,y_k\) 为 \(x\) 的孩子，按链接到 \(x\) 的先后排序。则 \(y_1.degree\ge0\)，且对 \(i=2,\dots,k\)，\(y_i.degree\ge i-2\)。 证明：\(y_i\) 被链接到 \(x\) 时，\(y_1,\dots,y_{i-1}\) 都已是 \(x\) 的孩子，故 \(x.degree\ge i-1\)；CONSOLIDATE 只链接度数相等的根，所以当时 \(y_i.degree\ge i-1\)。此后 \(y_i\) 至多失去一个孩子（失去两个就会被 CASCADING-CUT 从 \(x\) 剪下），故 \(y_i.degree\ge i-2\)。

斐波那契数：\(F_0=0\)，\(F_1=1\)，\(F_k=F_{k-1}+F_{k-2}\)（\(k\ge2\)）。名称由来就在这里。

引理 19.2：对所有 \(k\ge0\)，\(F_{k+2}=1+\sum_{i=0}^kF_i\)。（归纳：\(k=0\) 时 \(1+F_0=1=F_2\)；\(F_{k+2}=F_k+F_{k+1}=F_k+1+\sum_{i=0}^{k-1}F_i\)。）

引理 19.3：对所有 \(k\ge0\)，\(F_{k+2}\ge\phi^k\)。（归纳：\(F_2=1=\phi^0\)，\(F_3=2>\phi^1\)；\(k\ge2\) 时 \(F_{k+2}=F_{k+1}+F_k\ge\phi^{k-1}+\phi^{k-2}=\phi^{k-2}(\phi+1)=\phi^{k-2}\phi^2=\phi^k\)，用到 \(\phi^2=\phi+1\)。）

引理 19.4：设 \(k=x.degree\)，则 \(\mathrm{size}(x)\ge F_{k+2}\ge\phi^k\)。 证明：令 \(s_k\) 为任何斐波那契堆中度数为 \(k\) 的结点的最小可能 size，\(s_0=1\)，\(s_1=2\)，\(s_k\) 关于 \(k\) 单调不减。取度数 \(k\)、size 为 \(s_k\) 的结点 \(z\)，计 \(z\) 自身 1 个、第一个孩子 \(y_1\) 至少 1 个，再由引理 19.1 和单调性：

推论 19.5：\(n\) 结点斐波那契堆中任一结点的最大度数 \(D(n)=O(\lg n)\)。由 \(n\ge\mathrm{size}(x)\ge\phi^k\) 得 \(k\le\log_\phi n\)，且 \(k\) 为整数，\(k\le\lfloor\log_\phi n\rfloor\)。

于是 EXTRACT-MIN 与 DELETE 摊还 \(O(\lg n)\)。

习题 19.4 概括：19.4-1 斐波那契堆的高度不一定是 \(O(\lg n)\)——构造一串操作使堆只含一棵 \(n\) 个结点的线性链；19.4-2 若改为失去第 \(k\) 个孩子才级联切断，\(k\) 取何值时仍有 \(D(n)=O(\lg n)\)（任意常数 \(k\) 都可以）。

第 19 章思考题（PDF p.547–551）

• 19-1 删除的另一种实现（PISANO-DELETE：若 \(x\) 是最小结点则 EXTRACT-MIN，否则剪下 \(x\)、级联切断、把 \(x\) 的孩子表加入根表、从根表删除 \(x\)）：(a) 第 7 行把孩子表加入根表并非 \(O(1)\)，因为要逐个把孩子的父指针置空并清除标记；(b) 实际时间界用 \(x.degree\) 与 \(c\) 表示；(c) 用 \(x.degree,c,t(H),m(H)\) 给出结果堆的势能界；(d) 结论：摊还时间并不比 FIB-HEAP-DELETE 更好。
• 19-2 二项树与二项堆：二项树 \(B_k\) 递归定义——\(B_0\) 是单结点，\(B_k\) 由两棵 \(B_{k-1}\) 链接而成（一棵的根是另一棵根的最左孩子）。(a) \(B_k\) 有 \(2^k\) 个结点、高度 \(k\)、深度 \(i\) 处恰有 \(\binom ki\) 个结点、根度数 \(k\) 最大，且根的孩子从左到右依次是 \(B_{k-1},\dots,B_0\) 的根。二项堆：一组满足最小堆性质的二项树，每个度数至多一棵。(b) 二项堆中的树对应 \(n\) 的二进制表示，至多 \(\lfloor\lg n\rfloor+1\) 棵；(c) 用左孩子右兄弟表示法，根表按度数递增的单链表，实现七种操作，每个最坏 \(O(\lg n)\)，MAKE-HEAP \(O(1)\)；(d) 只实现可合并堆操作时斐波那契堆中的树是（无序）二项树，最大度数 ≤ \(\lfloor\lg n\rfloor\)；(e) McGee 堆：插入与合并后也执行 consolidate，分析最坏运行时间。
• 19-3 更多斐波那契堆操作：(a) FIB-HEAP-CHANGE-KEY(H,x,k)，分 \(k\) 大于、小于、等于 \(x.key\) 三种情况分析摊还时间（增大关键字可用删除再插入，\(O(\lg n)\)）；(b) FIB-HEAP-PRUNE(H,r) 删除 \(q=\min(r,H.n)\) 个任选结点，可能需修改结构与势函数。
• 19-4 2-3-4 堆：只在叶子存关键字（顺序任意），内部结点 \(x.small\) 存子树最小关键字，根存树高；放主存。实现 MINIMUM、DECREASE-KEY、INSERT、DELETE、EXTRACT-MIN，各 \(O(\lg n)\)；UNION \(O(\lg n)\)。

本章注记（PDF p.551）：Fredman 与 Tarjan 提出斐波那契堆，并将其应用于单源最短路、全源最短路、带权二部图匹配和最小生成树。Driscoll、Gabow、Shrairman、Tarjan 提出"松弛堆"（relaxed heaps）：一种与斐波那契堆摊还界相同；另一种 DECREASE-KEY 为最坏 \(O(1)\)、EXTRACT-MIN 与 DELETE 最坏 \(O(\lg n)\)，在并行算法中也有优势。若 EXTRACT-MIN 返回值随时间单调递增且数据为有限范围整数，还有更快的结构（见第 6 章注记）。

第 19 章本章要点

• 斐波那契堆 = 最小堆有序树的集合 + 环形双向链表根表 + H.min；"懒惰"策略：INSERT/UNION 只往根表挂，EXTRACT-MIN 时才合并同度数的树。
• 势函数 \(\Phi=t(H)+2m(H)\)：根数项支付 CONSOLIDATE 中的链接，标记项（系数 2）支付级联切断。
• 摊还界：INSERT、MINIMUM、UNION、DECREASE-KEY 为 \(O(1)\)；EXTRACT-MIN、DELETE 为 \(O(\lg n)\)。
• 级联切断规则（失去第二个孩子就被切下）保证 \(\mathrm{size}(x)\ge F_{k+2}\ge\phi^k\)，从而最大度数 \(D(n)\le\lfloor\log_\phi n\rfloor\)——这是名字的由来。注意树高并不保证 \(O(\lg n)\)。
• 理论价值大于实用价值：实践中常数大、实现复杂，二叉堆/配对堆常更快。

与量化交易的关联

• 系统实现：优先队列是事件驱动回测引擎（按时间戳弹出下一个事件）、订单簿撮合（按价格-时间优先取最优挂单）、定时任务调度的核心。实际工程几乎都用二叉堆（Python heapq、C++ std::priority_queue）或配对堆；斐波那契堆的价值在于理解"DECREASE-KEY 能否 \(O(1)\)"对 Dijkstra/Prim 复杂度的影响。
• 需要频繁修改优先级（例如撤单、改单改变挂单在队列中的位置；或在套利路径搜索中更新最短距离）时，需要"带句柄的堆"（indexed heap），本章关于句柄的讨论直接适用。
• 摊还界不保证单次延迟，低延迟系统中 EXTRACT-MIN 可能触发 \(O(n)\) 级的一次性合并，这是不选它的另一个理由。
• 与因子研究、风险建模等数学环节无直接关联。

推荐习题

• 19.2-1（手算一次 EXTRACT-MIN，熟悉 CONSOLIDATE）。
• 19.3-1、19.3-2（标记机制与聚合分析）。
• 19.4-1（树高不是 \(O(\lg n)\) 的反例，纠正常见误解）、19.4-2（级联阈值 \(k\) 的推广）。
• 思考题 19-2（二项堆，理解斐波那契堆的来源，并可练习写出完整实现）。

第 20 章 van Emde Boas 树（van Emde Boas Trees）（PDF p.552–581）

20.0 导言（PDF p.552–553）

二叉堆、红黑树、斐波那契堆都至少有一个重要操作需要 \(O(\lg n)\)（最坏或摊还）。这是比较模型的必然：若 INSERT 和 EXTRACT-MIN 都能 \(o(\lg n)\)，则 \(n\) 次插入加 \(n\) 次抽取就能在 \(o(n\lg n)\) 内排序，违反 8.1 节的 \(\Omega(n\lg n)\) 下界。但当关键字是有界整数时（如计数排序 \(\Theta(n+k)\)），可以绕过下界。

van Emde Boas 树（vEB 树）支持 SEARCH（这里用更简单的 MEMBER(S, x) 返回布尔值）、INSERT、DELETE、MINIMUM、MAXIMUM、SUCCESSOR、PREDECESSOR，每个最坏 \(O(\lg\lg u)\)。限制：关键字必须是 \(0\) 到 \(u-1\) 的整数，不允许重复；本章不讨论卫星数据。

• 记号：\(n\) 为集合中当前元素数，\(u\) 为可能取值范围。\(\{0,1,\dots,u-1\}\) 称为全域（universe），\(u\) 为全域大小（universe size）。始终假设 \(u=2^k\)，\(k\ge1\)。
• 约定：集合为空时 MINIMUM/MAXIMUM 返回 NIL；无后继/前驱时 SUCCESSOR/PREDECESSOR 返回 NIL。
• 路线：20.1 简单方法 → 20.2 原型 vEB 结构（递归但达不到 \(O(\lg\lg u)\)）→ 20.3 真正的 vEB 树。

20.1 预备方法（Preliminary approaches）（PDF p.553–557）

直接寻址（位向量）。 用 \(u\) 位数组 \(A[0..u-1]\)，\(A[x]=1\) 当且仅当 \(x\) 在集合中。INSERT、DELETE、MEMBER 为 \(O(1)\)；MINIMUM、MAXIMUM、SUCCESSOR、PREDECESSOR 最坏 \(\Theta(u)\)（例：集合只有 0 与 \(u-1\)，求 0 的后继要扫描 1 到 \(u-2\)）。

叠加二叉树。 在位向量上叠加一棵位二叉树：叶子是位向量，每个内部结点存其两个孩子的逻辑或（子树中有 1 则为 1）。图 20.1：\(u=16\)，集合 {2,3,4,5,7,14,15}。

• 最小值：从根向下，总走最左的含 1 结点；最大值对称。
• 后继：从叶子 \(x\) 向上，直到从左边进入某结点且其右孩子 \(z\) 为 1，然后在 \(z\) 子树中找最小值。前驱对称（图中 14 的前驱是 7）。
• 插入：把叶子到根路径上的位都置 1；删除：从叶子向上，每个结点重新计算两个孩子的或。
• 树高 \(\lg u\)，每个操作至多一趟上行一趟下行，\(O(\lg u)\)。只比红黑树略好：MEMBER 仍为 \(O(1)\)（红黑树 \(O(\lg n)\)），但若 \(n\ll u\)，红黑树在其他操作上更快。

叠加常数高度的树。 设 \(u=2^{2k}\)，\(\sqrt u\) 为整数。叠加度为 \(\sqrt u\) 的树，高度恒为 2（图 20.2）。深度 1 的 \(\sqrt u\) 个结点可看作数组 \(summary[0..\sqrt u-1]\)，\(summary[i]=1\) 当且仅当子数组 \(A[i\sqrt u..(i+1)\sqrt u-1]\)（称为第 \(i\) 个簇 cluster）含 1。\(A[x]\) 位于第 \(\lfloor x/\sqrt u\rfloor\) 簇。

• INSERT 为 \(O(1)\)：置 \(A[x]\) 和 \(summary[\lfloor x/\sqrt u\rfloor]\) 为 1。
• 最小（最大）值：在 summary 中找最左（最右）的 1，比如 \(summary[i]\)，再在第 \(i\) 簇中线性查找。
• 后继（前驱）：先在 \(x\) 的簇内向右（左）找；找不到则令 \(i=\lfloor x/\sqrt u\rfloor\)，在 summary 中从 \(i\) 向右（左）找第一个 1，得到簇号，再在该簇中找最左（最右）的 1。
• 删除：令 \(i=\lfloor x/\sqrt u\rfloor\)，置 \(A[x]=0\)，再把 \(summary[i]\) 设为第 \(i\) 簇所有位的或。
• 每个操作至多搜索两个 \(\sqrt u\) 位的簇加 summary，\(O(\sqrt u)\)。看似倒退（比 \(O(\lg u)\) 慢），但"度为 \(\sqrt u\) 的树"正是 vEB 树的关键思想。

习题 20.1 概括：20.1-1 支持重复关键字；20.1-2 支持卫星数据；20.1-3 这些结构找后继/前驱不要求 \(x\) 在集合中——说明在 BST 中如何找不在树中的 \(x\) 的后继；20.1-4 改为度 \(u^{1/k}\)（\(k>1\) 常数）的树，高度与各操作时间（高度 \(k\)，操作 \(O(ku^{1/k})\)）。

20.2 递归结构（A recursive structure）（PDF p.557–566）

把"度为 \(\sqrt u\)"的想法递归化：全域大小每层开平方——\(u\) 的结构含 \(u^{1/2}\) 个项，每项是 \(u^{1/4}\) 的结构，……直到基础大小 2。本节假设 \(u=2^{2^k}\)（只允许 2, 4, 16, 256, 65536, …，实际太受限，20.3 节放宽）。

目标递推式。 已知 \(T(n)=2T(\lfloor\sqrt n\rfloor)+\lg n\)（20.1）的解为 \(O(\lg n\lg\lg n)\)。考虑更简单的

• 设计原则：每层花常数时间，然后只递归进入一个规模为 \(\sqrt u\) 的子结构。
• 另一种理解：存储全域大小需 \(\lg u\) 位，每层位数减半；从 \(b\) 位减半到 1 位需 \(\lg b\) 层，\(b=\lg u\)，所以 \(\lg\lg u\) 层后全域大小为 2。

下标函数。 把 \(x\) 视作 \(\lg u\) 位二进制数：簇号为高 \((\lg u)/2\) 位，簇内位置为低 \((\lg u)/2\) 位。

20.2.1 原型 vEB 结构（proto-vEB）

proto-vEB(\(u\)) 递归定义，每个结构有属性 \(u\)：

• 若 \(u=2\)：基础大小，含两位数组 \(A[0..1]\)。
• 否则 \(u=2^{2^k}\)（\(k\ge1\)，\(u\ge4\)），含：指针 summary 指向一个 proto-vEB(\(\sqrt u\))；数组 \(cluster[0..\sqrt u-1]\)，每项指向一个 proto-vEB(\(\sqrt u\))（图 20.3）。
• 元素 \(x\) 递归地存于第 \(\mathrm{high}(x)\) 号簇中，作为该簇的元素 \(\mathrm{low}(x)\)。与上一节的两层结构相比，这里用显式指针代替下标计算。
• 图 20.4：表示 {2,3,4,5,7,14,15} 的完全展开的 proto-vEB(16)。顶层有 4 个 proto-vEB(4) 簇和一个 proto-vEB(4) summary；每个 proto-vEB(4) 又有两个 proto-vEB(2) 簇和一个 proto-vEB(2) summary。基础层中一部分 proto-vEB(2) 存真实元素位（例："elements 6,7" 存 \(A[0]=0\)、\(A[1]=1\)），其余存 summary 位（例："clusters 2,3" 的 \(A[0]=0\) 表示簇 2（元素 8–11）全空，\(A[1]=1\) 表示簇 3（元素 12–15）非空）。

20.2.2 proto-vEB 上的操作

所有带参数 \(x\) 的操作假设 \(0\le x<V.u\)。

MEMBER（绕过 summary 直接下钻）：

def PROTO_VEB_MEMBER(V, x):
    if V.u == 2:
        return V.A[x]
    return PROTO_VEB_MEMBER(V.cluster[high(x)], low(x))

例：查询 6（\(u=16\)）：high(6)=1、low(6)=2 → 进入右上的 proto-vEB(4) 查元素 2；\(u=4\) 时 high(2)=1、low(2)=0 → 查对应 proto-vEB(2) 的 \(A[0]=0\)，返回 0，6 不在集合中。递推 \(T(u)=T(\sqrt u)+O(1)\)，\(O(\lg\lg u)\)。

MINIMUM：

def PROTO_VEB_MINIMUM(V):
    if V.u == 2:
        if V.A[0] == 1: return 0
        elif V.A[1] == 1: return 1
        else: return None
    min_cluster = PROTO_VEB_MINIMUM(V.summary)      # 第一个非空簇
    if min_cluster is None:
        return None
    offset = PROTO_VEB_MINIMUM(V.cluster[min_cluster])
    return index(min_cluster, offset)

两次递归：\(T(u)=2T(\sqrt u)+O(1)\)（20.3），换元后 \(S(m)=2S(m/2)+O(1)\)，主方法情形 1，\(S(m)=\Theta(m)\)，即 \(T(u)=\Theta(\lg u)\)，未达目标。

SUCCESSOR（不要求 \(x\) 在集合中）：

def PROTO_VEB_SUCCESSOR(V, x):
    if V.u == 2:
        return 1 if (x == 0 and V.A[1] == 1) else None
    offset = PROTO_VEB_SUCCESSOR(V.cluster[high(x)], low(x))   # 先在本簇找
    if offset is not None:
        return index(high(x), offset)
    succ_cluster = PROTO_VEB_SUCCESSOR(V.summary, high(x))     # 找下一个非空簇
    if succ_cluster is None:
        return None
    offset = PROTO_VEB_MINIMUM(V.cluster[succ_cluster])
    return index(succ_cluster, offset)

最坏两次递归加一次 MINIMUM：\(T(u)=2T(\sqrt u)+\Theta(\lg\sqrt u)=2T(\sqrt u)+\Theta(\lg u)\)，解为 \(\Theta(\lg u\lg\lg u)\)，比 MINIMUM 还慢。

INSERT：

def PROTO_VEB_INSERT(V, x):
    if V.u == 2:
        V.A[x] = 1
    else:
        PROTO_VEB_INSERT(V.cluster[high(x)], low(x))
        PROTO_VEB_INSERT(V.summary, high(x))       # 置该簇的 summary 位

两次递归，递推 (20.3)，\(\Theta(\lg u)\)。

DELETE 更复杂：插入时总可以把 summary 位置 1，但删除时不能总把它清 0，需要判断簇中是否还有 1——要么扫描簇的全部 \(\sqrt u\) 位，要么给结构加计数属性 \(n\)（习题 20.2-2、20.2-3）。

结论：必须让每个操作至多做一次递归调用，这是 20.3 节的任务。

习题 20.2 概括：20.2-1 写 PROTO-VEB-MAXIMUM 与 PROTO-VEB-PREDECESSOR；20.2-2 扫描簇来更新 summary 的 DELETE 及其最坏时间；20.2-3 加属性 \(n\) 后的 DELETE 及对其他过程的影响；20.2-4/20.2-5 支持重复关键字/卫星数据；20.2-6 创建 proto-vEB(\(u\))；20.2-7 证明 MINIMUM 第 9 行执行时结构为空；20.2-8 若每个簇数组只有 \(u^{1/4}\) 个元素，各操作时间如何。

20.3 van Emde Boas 树（The van Emde Boas tree）（PDF p.566–577）

proto-vEB 递归次数太多。vEB 树多存一点信息（min 与 max）来消除部分递归。同时放宽为 \(u\) 为任意 2 的幂：\(u\) 为 2 的奇数次幂时，把 \(\lg u\) 位分成高 \(\lceil(\lg u)/2\rceil\) 位与低 \(\lfloor(\lg u)/2\rfloor\) 位。定义上平方根 \(\sqrt[\uparrow]{u}=2^{\lceil(\lg u)/2\rceil}\) 与下平方根 \(\sqrt[\downarrow]{u}=2^{\lfloor(\lg u)/2\rfloor}\)，\(u=\sqrt[\uparrow]{u}\cdot\sqrt[\downarrow]{u}\)；\(u\) 为偶数次幂时两者都等于 \(\sqrt u\)。重新定义

20.3.1 vEB 树

vEB(\(u\))（\(u>2\)）包含（图 20.5）：全域大小 \(u\)；min（最小元素）；max（最大元素）；summary 指向 vEB(\(\sqrt[\uparrow]{u}\))；\(cluster[0..\sqrt[\uparrow]{u}-1]\) 指向 \(\sqrt[\uparrow]{u}\) 棵 vEB(\(\sqrt[\downarrow]{u}\))。

关键约定：

• min 中的元素不出现在任何簇中；vEB 树存储的元素 = \(V.min\) + 各簇中递归存储的元素。
• max 的处理不同：除非树中只有一个元素（min = max），max 中的元素也出现在簇中。
• vEB(2) 不需要数组 \(A\)，其元素可由 min、max 确定。空树无论 \(u\) 多大 min、max 均为 NIL。
• 图 20.6：表示 {2,3,4,5,7,14,15} 的 vEB(16)，\(V.min=2\)、\(V.max=15\)；虽然 high(2)=0，2 并不在 \(V.cluster[0]\) 中：\(V.cluster[0].min=3\)，且由于簇 0 只含 2、3，\(V.cluster[0]\) 内部的 vEB(2) 簇都是空的。

min/max 在四个方面减少递归：

1. MINIMUM、MAXIMUM 无需递归，直接返回。
2. SUCCESSOR 无需递归判断后继是否在 \(x\) 的簇中：后继在本簇当且仅当 \(x\) 严格小于该簇的 max；PREDECESSOR 与 min 对称。
3. 常数时间判断树中有 0 个（min = max = NIL）、1 个（min = max ≠ NIL）或至少 2 个元素（min ≠ max）。
4. 向空树插入只需设置 min 与 max，\(O(1)\)；从只有一个元素的树删除也只需改 min、max，\(O(1)\)。这能截断递归链。

运行时间递推。 所有操作满足

空间与创建代价。 使用前必须知道 \(u\)；vEB 树总空间 \(O(u)\)（思考题 20-1），创建空树需 \(O(u)\) 时间，而红黑树创建为 \(O(1)\)。所以操作次数很少时不划算；不过元素很少时通常直接用数组或链表。

20.3.2 vEB 树上的操作

由于 min 与 max 的不对称（至少两个元素时 min 不在簇中而 max 在），书中给出全部五个查询操作的伪代码。

MINIMUM / MAXIMUM：直接返回 V.min / V.max，\(O(1)\)。

MEMBER：

def VEB_TREE_MEMBER(V, x):
    if x == V.min or x == V.max:
        return True
    elif V.u == 2:
        return False          # vEB(2) 除 min、max 外没有其他元素
    else:
        return VEB_TREE_MEMBER(V.cluster[high(x)], low(x))

\(O(\lg\lg u)\)。

SUCCESSOR（每次只在簇或 summary 之一上递归）：

def VEB_TREE_SUCCESSOR(V, x):
    if V.u == 2:
        return 1 if (x == 0 and V.max == 1) else None
    elif V.min is not None and x < V.min:
        return V.min
    else:
        max_low = VEB_TREE_MAXIMUM(V.cluster[high(x)])
        if max_low is not None and low(x) < max_low:      # 后继在本簇
            offset = VEB_TREE_SUCCESSOR(V.cluster[high(x)], low(x))
            return index(high(x), offset)
        else:                                              # 去 summary 找下一非空簇
            succ_cluster = VEB_TREE_SUCCESSOR(V.summary, high(x))
            if succ_cluster is None:
                return None
            offset = VEB_TREE_MINIMUM(V.cluster[succ_cluster])
            return index(succ_cluster, offset)

根据第 8 行判断，只在第 9 行（全域 \(\sqrt[\downarrow]{u}\)）或第 11 行（全域 \(\sqrt[\uparrow]{u}\)）之一递归，其余（含 MINIMUM/MAXIMUM 调用）\(O(1)\)，最坏 \(O(\lg\lg u)\)。

PREDECESSOR：与 SUCCESSOR 对称，但多一种情况。

def VEB_TREE_PREDECESSOR(V, x):
    if V.u == 2:
        return 0 if (x == 1 and V.min == 0) else None
    elif V.max is not None and x > V.max:
        return V.max
    else:
        min_low = VEB_TREE_MINIMUM(V.cluster[high(x)])
        if min_low is not None and low(x) > min_low:
            offset = VEB_TREE_PREDECESSOR(V.cluster[high(x)], low(x))
            return index(high(x), offset)
        else:
            pred_cluster = VEB_TREE_PREDECESSOR(V.summary, high(x))
            if pred_cluster is None:
                if V.min is not None and x > V.min:   # 额外情况：前驱是不在任何簇中的 min
                    return V.min
                return None
            offset = VEB_TREE_MAXIMUM(V.cluster[pred_cluster])
            return index(pred_cluster, offset)

额外情况的原因：后继若不在本簇必在编号更大的簇中；但前驱若是 \(V.min\)，它不在任何簇中。仍为 \(O(\lg\lg u)\)。

INSERT（只做一次递归）：插入元素时，若其簇已有元素，簇号已在 summary 中，无需递归更新 summary；若簇为空，元素成为簇中唯一元素，插入空树只需 \(O(1)\)。

def VEB_EMPTY_TREE_INSERT(V, x):
    V.min = x; V.max = x

def VEB_TREE_INSERT(V, x):              # 假设 x 不在集合中
    if V.min is None:
        VEB_EMPTY_TREE_INSERT(V, x)
    else:
        if x < V.min:
            x, V.min = V.min, x          # x 成为新 min，把原 min 插入簇中
        if V.u > 2:
            if VEB_TREE_MINIMUM(V.cluster[high(x)]) is None:   # 目标簇为空
                VEB_TREE_INSERT(V.summary, high(x))
                VEB_EMPTY_TREE_INSERT(V.cluster[high(x)], low(x))  # O(1)
            else:
                VEB_TREE_INSERT(V.cluster[high(x)], low(x))
        if x > V.max:
            V.max = x

两个分支各只有一次真正的递归（全域至多 \(\sqrt[\uparrow]{u}\)），\(O(\lg\lg u)\)。基础情况 vEB(2) 非空时，第 3–4 行与第 10–11 行能正确更新 min、max。

DELETE（假设 \(x\) 在集合中）：

def VEB_TREE_DELETE(V, x):
    if V.min == V.max:                   # 只有一个元素
        V.min = None; V.max = None
    elif V.u == 2:                       # 基础情况，两个元素
        V.min = 1 if x == 0 else 0
        V.max = V.min
    else:
        if x == V.min:                   # 删除 min：把次小元素提为新 min，转而从簇中删它
            first_cluster = VEB_TREE_MINIMUM(V.summary)
            x = index(first_cluster, VEB_TREE_MINIMUM(V.cluster[first_cluster]))
            V.min = x
        VEB_TREE_DELETE(V.cluster[high(x)], low(x))
        if VEB_TREE_MINIMUM(V.cluster[high(x)]) is None:   # 簇变空
            VEB_TREE_DELETE(V.summary, high(x))
            if x == V.max:
                summary_max = VEB_TREE_MAXIMUM(V.summary)
                if summary_max is None:
                    V.max = V.min        # 只剩 min
                else:
                    V.max = index(summary_max, VEB_TREE_MAXIMUM(V.cluster[summary_max]))
        elif x == V.max:                 # 簇未空，但可能需更新 max
            V.max = index(high(x), VEB_TREE_MAXIMUM(V.cluster[high(x)]))

• 第 17 行调用 MAXIMUM(V.summary) 有效，因为已递归删除过 summary，其 max 已更新；第 20、22 行同样依赖第 13 行递归已更正簇的 max。
• 复杂度：看似可能两次递归（第 13 行与第 15 行），但第 15 行执行的前提是 \(x\) 的簇变空，这说明第 13 行递归时 \(x\) 是簇中唯一元素，那次递归只执行第 1–3 行，耗时 \(O(1)\)。两种互斥情形：要么第 13 行递归为常数时间，要么第 15 行不发生。递推 (20.4) 成立，最坏 \(O(\lg\lg u)\)。

习题 20.3 概括：20.3-1/20.3-2 支持重复关键字/卫星数据；20.3-3 写创建空 vEB 树的过程；20.3-4 对已存在元素调用 INSERT、对不存在元素调用 DELETE 会怎样，以及如何 \(O(1)\) 检查元素是否存在；20.3-5 改为 \(u^{1/k}\) 个簇、每簇全域 \(u^{1-1/k}\) 时各操作时间；20.3-6 计入 \(O(u)\) 创建时间时，至少多少次操作才能使摊还时间为 \(O(\lg\lg u)\)（\(n=\Omega(u/\lg\lg u)\)）。

第 20 章思考题（PDF p.578–580）

• 20-1 vEB 树的空间：(a) 空间递推 \(P(u)=(\sqrt u+1)P(\sqrt u)+\Theta(\sqrt u)\)（20.5）；(b) 解为 \(P(u)=O(u)\)。缩减空间 vEB 树（RS-vEB）：cluster 改为用动态表（17.4 节）实现的散列表，只存非空簇；所有簇为空时 summary 为 NIL；插入空 RS-vEB 树时调用 CREATE-NEW-RS-VEB-TREE(u) 创建（设 \(u\)、min=max=summary=NIL、空的动态散列表）。(c)(d) 写 RS-VEB-TREE-INSERT 与 RS-VEB-TREE-SUCCESSOR；(e) 简单均匀散列假设下它们为 \(O(\lg\lg u)\) 期望摊还时间；(f) 无删除时空间 \(O(n)\)；(g) 创建空 RS-vEB 树只需 \(O(1)\)。
• 20-2 y-fast trie（Willard）：MEMBER、MINIMUM、MAXIMUM、PREDECESSOR、SUCCESSOR 最坏 \(O(\lg\lg u)\)，INSERT、DELETE 摊还 \(O(\lg\lg u)\)，空间 \(O(n)\)，依赖完全散列（11.5 节）。预备结构：完全散列表存储每个元素二进制表示的所有前缀（例 \(u=16\)、\(x=13=1101\)，存 1、11、110、1101），外加按序双向链表。(a) 空间 \(O(n\lg u)\)；(b) MIN/MAX \(O(1)\)，MEMBER/PRED/SUCC \(O(\lg\lg u)\)（对前缀长度二分查找），INSERT/DELETE \(O(\lg u)\)。改进：把 \(n\) 个元素按序分成 \(n/\lg u\) 组，每组 \(\lg u\) 个，存于平衡 BST；每组选一个代表（≥ 组内最大、< 下一组所有元素），散列表只存代表。(c)–(h) 证明空间 \(O(n)\)，各操作的时间，以及放宽组大小使插入删除摊还 \(O(\lg\lg u)\)。

本章注记（PDF p.580–581）：以 P. van Emde Boas 命名（1975 年提出早期形式，后与 Kaas、Zijlstra 改进）；Mehlhorn 与 Näher 推广到全域大小为素数的情形；Dementiev 等基于其思想设计了非递归三层搜索树，实验中更快；Wang 与 Lin 设计了硬件流水线版本，每个操作摊还常数时间、流水线 \(O(\lg\lg u)\) 级；Pătraşcu 与 Thorup 的下界表明 vEB 树对前驱查询是最优的（即使允许随机化）。

第 20 章本章要点

• 关键字为 \(\{0,\dots,u-1\}\) 中的整数时，可以突破比较模型下界：vEB 树七种动态集合操作均为最坏 \(O(\lg\lg u)\)。
• 设计思想：按 \(\sqrt u\) 递归分簇（高位 = 簇号，低位 = 簇内偏移），加一个 summary 记录非空簇；目标递推 \(T(u)=T(\sqrt u)+O(1)\Rightarrow O(\lg\lg u)\)。
• proto-vEB 因每层两次递归只能达到 \(\Theta(\lg u)\) 或 \(\Theta(\lg u\lg\lg u)\)；vEB 树通过存 min/max（且 min 不下放到簇）使每个操作只递归一次。
• 代价：空间与创建时间 \(O(u)\)；RS-vEB 树或 y-fast trie 可把空间降到 \(O(n)\)。

与量化交易的关联

• 订单簿实现：价格是以最小变动价位（tick）为单位的有界整数，非常适合整数域结构。撮合引擎需要快速求"最优买价/卖价"（MAXIMUM/MINIMUM）和"下一个有挂单的价位"（SUCCESSOR/PREDECESSOR）。实际高性能撮合引擎常用的"按价位直接寻址数组 + 位图 + 分层 summary 位图"本质上就是 20.1 节常数高度树的变体（配合 CPU 的 ctz/clz 指令一次处理 64 位），vEB 树给出了其渐近极限。
• 时间戳也是有界整数，事件调度可以用整数优先队列（如日历队列、基数堆），原理同此。
• 与因子研究、风险建模等统计建模环节无直接关联。

推荐习题

• 20.1-4（度 \(u^{1/k}\) 树的权衡，对应多层位图的层数选择）。
• 20.2-2、20.2-3（理解为什么 proto-vEB 的删除困难）。
• 20.3-4、20.3-6（边界行为与创建代价的摊还）。
• 思考题 20-1（空间递推与 RS-vEB 树），20-2（y-fast trie，前缀散列的思想）。

第 21 章 用于不相交集合的数据结构（Data Structures for Disjoint Sets）（PDF p.582–606）

21.0 导言（PDF p.582）

有些应用需要把 \(n\) 个不同元素分成若干不相交集合，并支持两种操作：查找元素所在的唯一集合；合并两个集合。21.1 介绍操作与一个简单应用；21.2 链表实现；21.3 有根树表示（理论上超线性，实际上线性）；21.4 定义一个增长极快的函数及其增长极慢的反函数，并用复杂的摊还分析证明只比线性稍大的上界。

21.1 不相交集合操作（Disjoint-set operations）（PDF p.582–585）

不相交集合数据结构（disjoint-set data structure，也称并查集 union-find）维护不相交动态集合族 \(\mathcal S=\{S_1,\dots,S_k\}\)，每个集合用一个代表（representative）标识，代表是集合中某个成员。有的应用不关心选哪个成员，只要求集合未修改时两次查询返回同一代表；有的应用要求按规则选（如最小成员）。

每个元素用对象 \(x\) 表示，支持：

• MAKE-SET(x)：建立只含 \(x\) 的新集合，\(x\) 即代表；要求 \(x\) 不在其他集合中。
• UNION(x, y)：把含 \(x\) 的集合 \(S_x\) 与含 \(y\) 的集合 \(S_y\) 合并为并集（操作前两者不相交）；新代表可以是 \(S_x\cup S_y\) 中任一成员，很多实现选 \(S_x\) 或 \(S_y\) 的代表。概念上销毁 \(S_x,S_y\)；实践中常把一个集合的元素并入另一个。
• FIND-SET(x)：返回含 \(x\) 的唯一集合的代表的指针。

分析参数：\(n\) = MAKE-SET 操作数，\(m\) = MAKE-SET、UNION、FIND-SET 总操作数。每次 UNION 使集合数减 1，所以 UNION 至多 \(n-1\) 次；\(m\ge n\)；假设前 \(n\) 个操作都是 MAKE-SET。

应用：无向图的连通分量。 图 21.1：顶点 a–j、四个连通分量 {a,b,c,d}、{e,f,g}、{h,i}、{j}。按边 (b,d)、(e,g)、(a,c)、(h,i)、(a,b)、(e,f)、(b,c) 处理时集合族的演变（处理 (b,c) 时两者已在同一集合，不再合并）。

def CONNECTED_COMPONENTS(G):
    for v in G.V:
        MAKE_SET(v)
    for (u, v) in G.E:
        if FIND_SET(u) != FIND_SET(v):
            UNION(u, v)

def SAME_COMPONENT(u, v):
    return FIND_SET(u) == FIND_SET(v)

• 处理完所有边后，两顶点在同一连通分量当且仅当它们在同一集合（习题 21.1-2）。
• 边静态不变时，用深度优先搜索求连通分量更快（习题 22.3-12）；但边动态加入时，并查集比每加一条边就重新 DFS 更高效。
• 实际实现中图的顶点对象与并查集对象需要互相引用。

习题 21.1 概括：21.1-1 对给定 11 个顶点、11 条边的图按序处理并列出每步的分量；21.1-2 证明正确性；21.1-3 有 \(k\) 个连通分量时 FIND-SET 被调用 \(2|E|\) 次、UNION 被调用 \(|V|-k\) 次。

21.2 不相交集合的链表表示（Linked-list representation of disjoint sets）（PDF p.585–589）

结构（图 21.2）：每个集合一个链表。集合对象有 head（指向第一个对象）和 tail（指向最后一个对象）；链表中每个对象含一个集合成员、指向下一对象的指针、以及指回集合对象的指针。链表内顺序任意，代表是第一个对象中的成员。例：\(S_1=\{d,f,g\}\) 代表 \(f\)；\(S_2=\{b,c,e,h\}\) 代表 \(c\)。

• MAKE-SET(x)：新建只含 \(x\) 的链表，\(O(1)\)。
• FIND-SET(x)：沿 \(x\) 指回集合对象的指针，返回 head 所指成员，\(O(1)\)。例 FIND-SET(g) 返回 \(f\)。

简单 UNION。 UNION(x, y) 把 \(y\) 的链表接到 \(x\) 的链表尾部（用 tail 指针快速定位），\(x\) 的代表成为新代表，销毁 \(y\) 的集合对象。问题：必须更新原 \(y\) 链表中每个对象指回集合对象的指针，时间与 \(y\) 链表长度成线性。例：UNION(g, e) 需要更新 b、c、e、h 的指针。

最坏情况构造（图 21.3）：对象 \(x_1,\dots,x_n\)，先 \(n\) 次 MAKE-SET，再 UNION(\(x_2,x_1\))、UNION(\(x_3,x_2\))、…、UNION(\(x_n,x_{n-1}\))，\(m=2n-1\)。第 \(i\) 次 UNION 更新 \(i\) 个对象，总计 \(\sum_{i=1}^{n-1}i=\Theta(n^2)\)，每个操作平均（摊还）\(\Theta(n)\)。

加权合并启发式（weighted-union heuristic）：每个链表维护长度，总把较短的链表接到较长的链表上（平局任意）。单次 UNION 在两集合都有 \(\Omega(n)\) 成员时仍可能 \(\Omega(n)\)，但整体有好界：

定理 21.1：用链表表示与加权合并启发式，\(m\) 个 MAKE-SET、UNION、FIND-SET 操作（其中 \(n\) 个 MAKE-SET）耗时 \(O(m+n\lg n)\)。 证明：至多 \(n-1\) 次 UNION。对任一对象 \(x\)，每次其指针被更新时 \(x\) 都在较小的集合中，所以第一次更新后所在集合至少 2 个成员，第二次后至少 4 个……对任意 \(k\le n\)，更新 \(\lceil\lg k\rceil\) 次后集合至少 \(k\) 个成员。最大集合至多 \(n\) 个成员，所以每个对象指针至多更新 \(\lceil\lg n\rceil\) 次，所有 UNION 中更新对象指针的总时间 \(O(n\lg n)\)；更新 tail 与长度每次 \(\Theta(1)\)。MAKE-SET 与 FIND-SET 各 \(O(1)\)，共 \(O(m)\)。总计 \(O(m+n\lg n)\)。

习题 21.2 概括：21.2-1 写出带加权合并的链表版三个操作伪代码；21.2-2 对一段给定程序（16 个 MAKE-SET 后按步长合并）画出结果并给出 FIND-SET 答案；21.2-3 把聚合证明改为摊还界：MAKE-SET、FIND-SET \(O(1)\)，UNION \(O(\lg n)\)；21.2-4 图 21.3 序列在加权合并下的紧界（\(\Theta(n)\)）；21.2-5 每个集合对象只保留一个指针（以链表尾作为代表）；21.2-6 不保留 tail 指针，改为把一个链表拼接（splice）到另一个链表第一个元素之后。

21.3 不相交集合森林（Disjoint-set forests）（PDF p.588–593）

表示（图 21.4）：用有根树表示集合，每个结点含一个成员，每棵树代表一个集合。每个成员只指向父结点；根含代表且是自己的父结点。例：{b,c,e,h} 以 \(c\) 为根，{d,f,g} 以 \(f\) 为根；UNION(e,g) 后 \(c\) 的树挂到 \(f\) 下。

• MAKE-SET：建单结点树。
• FIND-SET：沿父指针找到根；途经结点构成查找路径（find path）。
• UNION：让一棵树的根指向另一棵树的根。
• 朴素实现不比链表快：\(n-1\) 次 UNION 可能造出 \(n\) 个结点的线性链。

两个启发式：

1. 按秩合并（union by rank）：类似加权合并。不显式维护子树大小，而是为每个结点维护秩（rank）——结点高度的上界（从后代叶子到该结点最长简单路径的边数）。UNION 时让秩小的根指向秩大的根。
2. 路径压缩（path compression）：在 FIND-SET 中让查找路径上每个结点直接指向根（图 21.5）。路径压缩不改变任何秩。

伪代码（x.p 为父结点）：

def MAKE_SET(x):
    x.p = x
    x.rank = 0

def UNION(x, y):
    LINK(FIND_SET(x), FIND_SET(y))

def LINK(x, y):              # x, y 都是根
    if x.rank > y.rank:
        y.p = x
    else:
        x.p = y
        if x.rank == y.rank:
            y.rank += 1      # 秩相等时任选一个作父亲并把其秩加 1

def FIND_SET(x):             # 两趟法：递归上行找根，回溯时逐个指向根
    if x != x.p:
        x.p = FIND_SET(x.p)
    return x.p

• 秩的规则：MAKE-SET 初始秩 0；FIND-SET 不改秩；UNION 时两根秩不等则秩高者为父、秩不变；秩相等则任选一个为父并把它的秩加 1。
• FIND-SET 是两趟方法（two-pass method）：递归时一趟向上找根，递归返回时一趟向下把每个结点更新为直接指向根。

启发式的效果。

• 只用按秩合并：\(O(m\lg n)\)（习题 21.4-4），且是紧的（习题 21.3-3）。
• 只用路径压缩（书中未证明）：\(n\) 次 MAKE-SET（因此至多 \(n-1\) 次 UNION）和 \(f\) 次 FIND-SET，最坏 \(\Theta\big(n+f\cdot(1+\log_{2+f/n}n)\big)\)。
• 两者同时用：最坏 \(O(m\,\alpha(n))\)，\(\alpha(n)\) 增长极慢，在任何可想象的应用中 \(\alpha(n)\le4\)，实践上可视为关于 \(m\) 线性（严格说是超线性）。21.4 节证明。

空间：每个元素 \(O(1)\)（父指针 + 秩），秩只需 \(O(\lg\lg n)\) 位（习题 21.4-3）。

习题 21.3 概括：21.3-1 用森林重做 21.2-2；21.3-2 写非递归的带路径压缩 FIND-SET；21.3-3 构造只用按秩合并时 \(\Omega(m\lg n)\) 的序列；21.3-4 加一个属性（循环链表指针）使 PRINT-SET(x) 的时间与集合大小成线性；21.3-5（星号）所有 LINK 都在 FIND-SET 之前时，两种启发式合用为 \(O(m)\)；只用路径压缩会怎样。

21.4 按秩合并与路径压缩的分析（Analysis of union by rank with path compression）（PDF p.594–603，选读节）

增长极快的函数。 对整数 \(k\ge0\)、\(j\ge1\)，

• 引理 21.2：\(A_1(j)=2j+1\)。（先归纳证 \(A_0^{(i)}(j)=j+i\)，于是 \(A_1(j)=A_0^{(j+1)}(j)=2j+1\)。）
• 引理 21.3：\(A_2(j)=2^{j+1}(j+1)-1\)。（先归纳证 \(A_1^{(i)}(j)=2^i(j+1)-1\)。）
• 数值：\(A_0(1)=2\)，\(A_1(1)=3\)，\(A_2(1)=7\)，\(A_3(1)=A_2(A_2(1))=A_2(7)=2^8\cdot8-1=2^{11}-1=2047\)，\(A_4(1)=A_3(2047)=A_2^{(2048)}(2047)\gg A_2(2047)=2^{2048}\cdot2048-1>2^{2048}=16^{512}\gg10^{80}\)（可观测宇宙原子数的估计）。

反函数：\(\alpha(n)=\min\{k:A_k(1)\ge n\}\)，即使 \(A_k(1)\ge n\) 的最低级。

秩的性质。

• 引理 21.4：对所有结点 \(x\)，\(x.rank\le x.p.rank\)，若 \(x\ne x.p\) 则严格小于。\(x.rank\) 初值为 0，随时间增加直到 \(x\ne x.p\)，此后不变。\(x.p.rank\) 随时间单调递增。（对操作次数归纳，习题 21.4-1。）
• 推论 21.5：沿任一结点到根的简单路径，秩严格递增。
• 引理 21.6：每个结点的秩至多 \(n-1\)。（秩只在 LINK 时增加，至多 \(n-1\) 次 LINK，每次至多使一个结点秩加 1。实际上秩 ≤ \(\lfloor\lg n\rfloor\)，习题 21.4-2，但弱界已够用。）

化归到 LINK。 分析中把每个 UNION 视为两个 FIND-SET 加一个 LINK。

• 引理 21.7：若把含 \(m'\) 个操作的序列 \(S'\) 转成含 \(m\) 个 MAKE-SET、LINK、FIND-SET 的序列 \(S\)，且 \(S\) 在 \(O(m\alpha(n))\) 内完成，则 \(S'\) 在 \(O(m'\alpha(n))\) 内完成。因为 \(m'\le m\le3m'\)。

势函数。 第 \(q\) 次操作后给每个结点 \(x\) 一个势 \(\phi_q(x)\)，森林势 \(\Phi_q=\sum_x\phi_q(x)\)，\(\Phi_0=0\)，且始终非负。

• 若 \(x\) 是根或 \(x.rank=0\)：\(\phi_q(x)=\alpha(n)\cdot x.rank\)。
• 若 \(x\) 不是根且 \(x.rank\ge1\)，先定义两个辅助函数：
  • \(\mathrm{level}(x)=\max\{k:x.p.rank\ge A_k(x.rank)\}\)，即对 \(x\) 的秩施加 \(A_k\) 后仍不超过父亲秩的最大级 \(k\)。满足
    \[0\le\mathrm{level}(x)<\alpha(n).\tag{21.1}\]
    下界：\(x.p.rank\ge x.rank+1=A_0(x.rank)\)；上界：\(A_{\alpha(n)}(x.rank)\ge A_{\alpha(n)}(1)\ge n>x.p.rank\)。由于 \(x.p.rank\) 单调增，\(\mathrm{level}(x)\) 随时间单调增。
  • \(\mathrm{iter}(x)=\max\{i:x.p.rank\ge A^{(i)}_{\mathrm{level}(x)}(x.rank)\}\)，即可以对 \(x\) 的秩迭代施加 \(A_{\mathrm{level}(x)}\) 多少次仍不超过父亲秩。满足
    \[1\le\mathrm{iter}(x)\le x.rank.\tag{21.2}\]
    下界：\(x.p.rank\ge A_{\mathrm{level}(x)}(x.rank)=A^{(1)}_{\mathrm{level}(x)}(x.rank)\)；上界：\(A^{(x.rank+1)}_{\mathrm{level}(x)}(x.rank)=A_{\mathrm{level}(x)+1}(x.rank)>x.p.rank\)。只要 \(\mathrm{level}(x)\) 不变，\(\mathrm{iter}(x)\) 只增不减；\(\mathrm{iter}(x)\) 要减小，\(\mathrm{level}(x)\) 必须增大。
  • 于是 \(\phi_q(x)=(\alpha(n)-\mathrm{level}(x))\cdot x.rank-\mathrm{iter}(x)\)。

引理 21.8：\(0\le\phi_q(x)\le\alpha(n)\cdot x.rank\)。（非根且秩 ≥1 时：取 level 最大 \(\alpha(n)-1\)、iter 最大 \(x.rank\) 得下界 \(x.rank-x.rank=0\)；取 level 最小 0、iter 最小 1 得上界 \(\alpha(n)x.rank-1\)。） 推论 21.9：若 \(x\) 非根且 \(x.rank>0\)，则 \(\phi_q(x)<\alpha(n)\cdot x.rank\)。

引理 21.10：设 \(x\) 非根，第 \(q\) 次操作是 LINK 或 FIND-SET，则 \(\phi_q(x)\le\phi_{q-1}(x)\)；若 \(x.rank\ge1\) 且 level 或 iter 改变，则 \(\phi_q(x)\le\phi_{q-1}(x)-1\)。证明：\(x.rank\) 与 \(\alpha(n)\) 都不变。若 level 不变而 iter 增大（至少 1），势至少降 1；若 level 增大（至少 1），\((\alpha(n)-\mathrm{level}(x))x.rank\) 至少降 \(x.rank\)，而 iter 至多降 \(x.rank-1\)，净降至少 1。

各操作的摊还代价：

• 引理 21.11：MAKE-SET 摊还 \(O(1)\)（新结点秩 0、势 0，其他不变）。
• 引理 21.12：LINK 摊还 \(O(\alpha(n))\)。设 LINK 让 \(y\) 成为 \(x\) 的父亲，实际代价 \(O(1)\)。势可能改变的只有 \(x\)、\(y\) 和 \(y\) 原来的孩子：\(y\) 的孩子势不增（引理 21.10）；\(x\) 原为根，势 \(\alpha(n)x.rank\)，之后若秩为 0 不变，否则由推论 21.9 下降；\(y\) 仍为根，秩不变或加 1，势增加 0 或 \(\alpha(n)\)。总增加 ≤ \(\alpha(n)\)。
• 引理 21.13：FIND-SET 摊还 \(O(\alpha(n))\)。设查找路径有 \(s\) 个结点，实际代价 \(O(s)\)。没有结点势增加（非根由引理 21.10，根的势不变）。证明至少 \(\max(0,s-(\alpha(n)+2))\) 个结点势降至少 1：取路径上满足"\(x.rank>0\)，且后面某处有非根结点 \(y\) 与它 level 相同"的结点 \(x\)；不满足者至多 \(\alpha(n)+2\) 个——路径首结点（若秩为 0）、根、以及每个 \(k=0,\dots,\alpha(n)-1\) 中 level 为 \(k\) 的最后一个结点。对这样的 \(x\)，令 \(k=\mathrm{level}(x)=\mathrm{level}(y)\)，\(i=\mathrm{iter}(x)\)，压缩前有 \(x.p.rank\ge A^{(i)}_k(x.rank)\)、\(y.p.rank\ge A_k(y.rank)\)、\(y.rank\ge x.p.rank\)，合并得
  \[y.p.rank\ge A_k(y.rank)\ge A_k(x.p.rank)\ge A_k(A^{(i)}_k(x.rank))=A^{(i+1)}_k(x.rank).\]
  路径压缩后 \(x\) 与 \(y\) 同父，\(x.p.rank=y.p.rank\) 且不减，故 \(x.p.rank\ge A^{(i+1)}_k(x.rank)\)：要么 iter 增至至少 \(i+1\)，要么 level 增大（当 iter 增至 \(x.rank+1\) 以上时）。由引理 21.10 势至少降 1。摊还代价 ≤ \(O(s)-(s-(\alpha(n)+2))=O(\alpha(n))\)（放大势能单位）。

定理 21.14：\(m\) 个 MAKE-SET、UNION、FIND-SET（其中 \(n\) 个 MAKE-SET）在采用按秩合并与路径压缩的不相交集合森林上，最坏时间 \(O(m\,\alpha(n))\)。（由引理 21.7、21.11–21.13 直接得到。）

习题 21.4 概括：21.4-1 证明引理 21.4；21.4-2 证明秩 ≤ \(\lfloor\lg n\rfloor\)；21.4-3 存储秩需要多少位（\(O(\lg\lg n)\)）；21.4-4 只用按秩合并时 \(O(m\lg n)\) 的简单证明；21.4-5 Dante 教授认为沿路径 level 单调递增，这是否正确（不正确）；21.4-6（星号）\(\alpha'(n)=\min\{k:A_k(1)\ge\lg(n+1)\}\)，实际中 ≤3，证明 \(O(m\alpha'(n))\) 界。

第 21 章思考题（PDF p.603–606）

• 21-1 离线最小值（Off-line minimum）：对 \(\{1..n\}\) 的动态集合执行 \(n\) 次 INSERT 与 \(m\) 次 EXTRACT-MIN，每个关键字恰插入一次，离线地确定每次 EXTRACT-MIN 的返回值 \(extracted[1..m]\)。(a) 实例 4, 8, E, 3, E, 9, 2, 6, E, E, E, 1, 7, E, 5 的答案（依次为 4, 3, 2, 6, 8, 1）。把序列写成 \(I_1,E,I_2,E,\dots,I_m,E,I_{m+1}\)，\(K_j\) 为 \(I_j\) 插入的关键字集合：

def OFF_LINE_MINIMUM(m, n):
    for i in range(1, n + 1):           # 按关键字从小到大
        j = index such that i in K[j]
        if j != m + 1:
            extracted[j] = i            # i 是第 j 次 EXTRACT-MIN 的结果
            l = smallest value > j for which K[l] still exists
            K[l] = K[j] | K[l]          # 合并，销毁 K[j]
    return extracted

(b) 证明正确性；(c) 用并查集高效实现并给出紧界（近线性 \(O(m\alpha(n))\) 量级）。

• 21-2 深度确定（Depth determination）：维护有根树森林，支持 MAKE-TREE(v)、FIND-DEPTH(v)、GRAFT(r, v)（把根 \(r\) 接为另一棵树中结点 \(v\) 的孩子）。(a) 朴素父指针实现最坏 \(\Theta(m^2)\)；改用并查集，每个结点维护"伪距离"\(v.d\)，使 \(v\) 到其集合根路径上的伪距离之和等于 \(v\) 在真实树中的深度。(b)–(d) 实现 MAKE-TREE、带路径压缩的 FIND-DEPTH、通过修改 UNION/LINK 实现 GRAFT，并正确维护伪距离（集合的根不一定是真实树的根）；(e) 最坏 \(O(m\alpha(n))\)。
• 21-3 Tarjan 离线最近公共祖先算法：有根树 \(T\) 中 \(u,v\) 的最近公共祖先（least common ancestor）是二者的公共祖先中最深的结点。给定结点对集合 \(P\)，求每对的 LCA。

def LCA(u):                         # 初始调用 LCA(T.root)，所有结点初始为 WHITE
    MAKE_SET(u)
    FIND_SET(u).ancestor = u
    for v in children(u):
        LCA(v)
        UNION(u, v)
        FIND_SET(u).ancestor = u
    u.color = BLACK
    for v such that {u, v} in P:
        if v.color == BLACK:
            print("LCA of", u, "and", v, "is", FIND_SET(v).ancestor)

(a) 每对恰打印一次；(b) 调用 LCA(u) 时集合数等于 \(u\) 的深度；(c) 正确性；(d) 用 21.3 节实现时的运行时间（近线性 \(O((n+|P|)\alpha(n))\)）。

本章注记（PDF p.606）：不相交集合的很多重要结果至少部分归功于 Tarjan，他用聚合分析首先给出以 Ackermann 函数反函数 \(\hat\alpha(m,n)\) 表示的紧上界（本节 \(A_k(j)\) 与 Ackermann 函数相似，\(\alpha(n)\) 与其反函数相似，两者对一切可想象的 \(m,n\) 都 ≤ 4）；更早 Hopcroft 与 Ullman 证明了 \(O(m\lg n)\) 界（实际是 \(O(m\lg^*n)\)）；21.4 节改编自 Tarjan 后来基于 Kozen 的分析；Harfst 与 Reingold 给出势能版证明。Tarjan 与 van Leeuwen 讨论了路径压缩的变体，包括常数因子更好的"一趟法"（如路径分裂、路径减半）。Gabow 与 Tarjan 证明某些应用中可达 \(O(m)\)。Tarjan 证明满足一定技术条件的任何并查集结构需要 \(\Omega(m\hat\alpha(m,n))\) 时间；Fredman 与 Saks 推广为最坏需访问 \(\Omega(m\hat\alpha(m,n))\) 个 \((\lg n)\) 位字。

第 21 章本章要点

• 并查集三操作：MAKE-SET、UNION、FIND-SET；参数 \(n\)（MAKE-SET 数）与 \(m\)（总操作数），UNION ≤ \(n-1\) 次。
• 链表实现：FIND-SET \(O(1)\)，UNION 需改写较短链表的回指针；加权合并给出 \(O(m+n\lg n)\)（每个元素至多被搬 \(\lg n\) 次——"小并大"思想）。
• 森林实现：按秩合并 + 路径压缩，\(O(m\,\alpha(n))\)，\(\alpha(n)\le4\) 实际为常数；单独用按秩合并为 \(O(m\lg n)\)。
• 分析工具：基于 \(A_k(j)\) 的 level/iter 势函数，关键引理是 FIND-SET 路径上除至多 \(\alpha(n)+2\) 个结点外势都降至少 1。

与量化交易的关联

• 风险建模/因子研究中的聚类：用并查集求图的连通分量可以实现基于阈值的资产聚类——把相关系数超过阈值的股票对连边，连通分量就是"高度相关组"；等价于单链接层次聚类（single-linkage clustering）在某个高度上的切割，常用于构造行业外的统计行业、去重高相关因子、配对交易候选池筛选。按相关系数从高到低逐条加边并用并查集合并，就得到完整的单链接聚类树（与第 23 章 Kruskal 算法本质相同）。
• 数据处理：处理公司更名、合并、代码变更时，把同一实体的多个标识符归并为一个等价类（实体解析 entity resolution）也是并查集的典型用法。
• 系统实现：思考题 16-4 的调度、21-3 的 LCA 也可用于任务依赖管理。
• 与定价、组合优化的数学推导无直接关联。

推荐习题

• 21.1-3（FIND-SET/UNION 调用次数）。
• 21.2-3（把聚合证明改写为摊还界）。
• 21.3-2（非递归路径压缩，工程实现必备）、21.3-3（只用按秩合并的下界）。
• 21.4-2、21.4-4（秩 ≤ \(\lg n\) 及其推论）。
• 思考题 21-1（离线最小值）、21-3（Tarjan 离线 LCA）。

第 VI 部分 图算法（Graph Algorithms）导言（PDF p.607–609）

图问题遍布计算机科学，数以百计的计算问题可以用图来表述。本部分内容：

• 第 22 章：图在计算机中的表示，基于广度优先搜索与深度优先搜索的算法，以及 DFS 的两个应用——有向无环图的拓扑排序、有向图分解为强连通分量。
• 第 23 章：最小权生成树——在每条边有权重时以最小总权重连接所有顶点，是贪心算法（第 16 章）的好例子。
• 第 24、25 章：边有长度/权重时的最短路径；第 24 章单源最短路径，第 25 章所有结点对最短路径。
• 第 26 章：流网络中的最大流（有源点、汇点、每条有向边有容量），可高效解决许多相关问题。

记号约定。 图 \(G=(V,E)\) 上算法的输入规模用两个参数 \(|V|\)、\(|E|\) 描述。在渐近记号内部（且仅在其中），\(V\) 表示 \(|V|\)、\(E\) 表示 \(|E|\)，如"\(O(VE)\)"即 \(O(|V||E|)\)。伪代码中用 \(G.V\)、\(G.E\) 表示顶点集和边集（视为图的属性）。

第 22 章 基本图算法（Elementary Graph Algorithms）（PDF p.610–644）

22.0 导言（PDF p.610）

本章介绍图的表示与搜索。搜索图指系统地沿边访问顶点；图搜索算法能揭示图的大量结构信息，很多算法以搜索输入图开始，图搜索技术是图算法的核心。22.1 邻接表与邻接矩阵；22.2 广度优先搜索与广度优先树；22.3 深度优先搜索及其访问顺序的标准结论；22.4 DFS 的第一个应用：有向无环图的拓扑排序；22.5 第二个应用：有向图的强连通分量。

22.1 图的表示（Representations of graphs）（PDF p.610–614）

图 \(G=(V,E)\) 的两种标准表示，对有向图与无向图都适用：

邻接表（adjacency list）：由 \(|V|\) 个链表组成的数组 \(Adj\)，对每个 \(u\in V\)，\(Adj[u]\) 包含所有满足 \((u,v)\in E\) 的顶点 \(v\)（或指向它们的指针）。伪代码中写作 G.Adj[u]。

• 有向图所有邻接表长度之和为 \(|E|\)；无向图为 \(2|E|\)（\((u,v)\) 使 \(u\) 出现在 \(v\) 的表中且反之亦然）。
• 空间 \(\Theta(V+E)\)；适合稀疏图（\(|E|\ll|V|^2\)），是本书多数算法的默认输入形式。
• 带权图：把权重 \(w(u,v)\) 与 \(v\) 一起存入 \(u\) 的邻接表，权函数 \(w:E\to\mathbb R\)。邻接表很灵活，可改造支持许多图变体。
• 缺点：判断边 \((u,v)\) 是否存在只能在 \(Adj[u]\) 中查找（习题 22.1-8 讨论用散列表等加速）。

邻接矩阵（adjacency matrix）：顶点任意编号为 \(1,\dots,|V|\)，\(|V|\times|V|\) 矩阵 \(A=(a_{ij})\)，\(a_{ij}=1\) 若 \((i,j)\in E\)，否则 0。

• 空间 \(\Theta(V^2)\)，与边数无关；适合稠密图（\(|E|\) 接近 \(|V|^2\)）或需快速判断两顶点间是否有边的场合（如第 25 章两个全源最短路算法）。
• 无向图的邻接矩阵对称，\(A=A^{\mathsf T}\)，可只存对角线及以上部分，内存几乎减半。
• 带权图：\(a_{uv}=w(u,v)\)，无边处存 NIL，或按问题方便存 0 或 \(\infty\)。
• 图较小时矩阵更简单；无权图每个元素只需 1 位。

图 22.1：5 个顶点、7 条边的无向图（边 1-2, 1-5, 2-3, 2-4, 2-5, 3-4, 4-5）的邻接表与邻接矩阵；图 22.2：6 个顶点、8 条边的有向图（边 1→2, 1→4, 2→5, 3→5, 3→6, 4→2, 5→4, 6→6）。

属性表示。 伪代码用 v.d 表示顶点属性、(u,v).f 表示边属性。实际程序中的实现方式取决于语言、算法和程序其他部分如何使用图：例如邻接表配上与 \(Adj\) 平行的数组 \(d[1..|V|]\)；或在面向对象语言中作为 Vertex 子类的实例变量。

习题 22.1 概括：22.1-1 由邻接表计算出度 \(O(V+E)\)、入度 \(O(V+E)\)；22.1-2 7 个顶点完全二叉树的两种表示；22.1-3 计算转置图 \(G^{\mathsf T}=(V,E^{\mathsf T})\)，\(E^{\mathsf T}=\{(v,u):(u,v)\in E\}\)（邻接表 \(O(V+E)\)，矩阵 \(O(V^2)\)）；22.1-4 多重图化简为去重边去自环的无向图，\(O(V+E)\)；22.1-5 有向图的平方 \(G^2\)（存在至多两条边的路径）；22.1-6 用邻接矩阵在 \(O(V)\) 时间判断通用汇点（universal sink，入度 \(|V|-1\)、出度 0）；22.1-7 关联矩阵 \(B\) 的 \(BB^{\mathsf T}\) 的含义（对角线为度数，非对角线为两顶点间边数的相反数）；22.1-8 邻接表改为散列表时查边的期望时间及缺点，替代方案（如有序数组/平衡树）。

22.2 广度优先搜索（Breadth-first search）（PDF p.615–623）

概述。 BFS 是最简单的图搜索算法之一，也是许多重要图算法的原型（Prim 最小生成树、Dijkstra 单源最短路使用类似思想）。给定图 \(G\) 与源点 \(s\)，BFS 系统地探索边以"发现"从 \(s\) 可达的每个顶点，计算 \(s\) 到每个可达顶点的距离（最少边数），并生成以 \(s\) 为根、含所有可达顶点的广度优先树；树中 \(s\) 到 \(v\) 的简单路径就是 \(G\) 中 \(s\) 到 \(v\) 的一条最短路径（边数最少）。有向图、无向图均适用。

• 名字由来：沿已发现/未发现顶点的边界均匀地向外扩展——发现所有距离 \(k\) 的顶点之后才发现距离 \(k+1\) 的顶点。
• 颜色：白（未发现）、灰、黑。顶点第一次被遇到时被发现，变为非白。若 \((u,v)\in E\) 且 \(u\) 为黑，则 \(v\) 为灰或黑——黑顶点的邻居都已被发现；灰顶点可能还有白邻居，它们构成边界。（区分灰黑只为帮助理解，习题 22.2-3 表明不区分结果相同。）
• 广度优先树：初始只有根 \(s\)。扫描已发现顶点 \(u\) 的邻接表时发现白顶点 \(v\)，就把 \(v\) 和边 \((u,v)\) 加入树，\(u\) 称为 \(v\) 的前驱（predecessor）或父结点。每个顶点至多被发现一次，因此至多一个父结点。

伪代码（邻接表输入；属性 u.color、前驱 u.π、距离 u.d；FIFO 队列 \(Q\) 管理灰色顶点）：

from collections import deque
def BFS(G, s):
    for u in G.V - {s}:
        u.color = WHITE; u.d = float('inf'); u.pi = None
    s.color = GRAY; s.d = 0; s.pi = None
    Q = deque([s])
    while Q:                          # 不变式：Q 恰为灰色顶点集合
        u = Q.popleft()
        for v in G.Adj[u]:
            if v.color == WHITE:
                v.color = GRAY
                v.d = u.d + 1
                v.pi = u
                Q.append(v)
        u.color = BLACK

• 图 22.3：在顶点 r, s, t, u, v, w, x, y 的无向图上从 \(s\) 运行 BFS 的过程，最终 \(d\)：\(s=0\)；\(r=w=1\)；\(v=t=x=2\)；\(u=y=3\)。
• BFS 结果（广度优先树）可能依赖第 12 行访问邻居的顺序，但距离 \(d\) 不依赖（习题 22.2-5）。

运行时间（聚合分析）：初始化后不会再把顶点涂白，第 13 行保证每个顶点至多入队、出队一次，队列操作共 \(O(V)\)；每个邻接表只在其顶点出队时扫描一次，总长度 \(\Theta(E)\)，扫描共 \(O(E)\)；初始化 \(O(V)\)。总时间 \(O(V+E)\)，与邻接表规模成线性。空间 \(O(V)\)（队列与属性）。

最短路径。 定义最短路径距离 \(\delta(s,v)\) 为 \(s\) 到 \(v\) 所有路径的最少边数，无路径时为 \(\infty\)；长度为 \(\delta(s,v)\) 的路径称为最短路径。（第 24、25 章推广到带权图；本章图无权，等价于边权均为 1。）

• 引理 22.1：对任意边 \((u,v)\in E\)，\(\delta(s,v)\le\delta(s,u)+1\)。（\(u\) 可达则 \(v\) 可达，且先走到 \(u\) 再走 \((u,v)\) 的路径长度为 \(\delta(s,u)+1\)；\(u\) 不可达时右边为 \(\infty\)。）
• 引理 22.2（上界）：BFS 结束时对每个 \(v\)，\(v.d\ge\delta(s,v)\)。对 ENQUEUE 次数归纳：基础 \(s.d=0=\delta(s,s)\)，其余为 \(\infty\)；发现白顶点 \(v\) 时 \(v.d=u.d+1\ge\delta(s,u)+1\ge\delta(s,v)\)，之后 \(v.d\) 不再改变。
• 引理 22.3（队列结构）：若队列为 \(\langle v_1,\dots,v_r\rangle\)（\(v_1\) 为头），则 \(v_r.d\le v_1.d+1\)，且 \(v_i.d\le v_{i+1}.d\)。即队列中至多两种不同的 \(d\) 值且非降。对队列操作次数归纳：出队时 \(v_r.d\le v_1.d+1\le v_2.d+1\)；入队 \(v\) 时，正在扫描的 \(u\) 已出队，新头 \(v_1.d\ge u.d\)，于是 \(v_{r+1}.d=v.d=u.d+1\le v_1.d+1\)，且 \(v_r.d\le u.d+1=v_{r+1}.d\)。
• 推论 22.4：若 \(v_i\) 在 \(v_j\) 之前入队，则 \(v_j\) 入队时 \(v_i.d\le v_j.d\)。
• 定理 22.5（BFS 正确性）：BFS 发现从 \(s\) 可达的每个顶点，结束时对所有 \(v\) 有 \(v.d=\delta(s,v)\)；且对可达的 \(v\ne s\)，一条从 \(s\) 到 \(v\) 的最短路径是：从 \(s\) 到 \(v.\pi\) 的最短路径再接边 \((v.\pi,v)\)。 证明（反证）：设 \(v\) 是 \(d\) 值错误的顶点中 \(\delta(s,v)\) 最小者，\(v\ne s\)，由引理 22.2 有 \(v.d>\delta(s,v)\)，且 \(v\) 可达。取最短路径上 \(v\) 的前一个顶点 \(u\)，\(\delta(s,v)=\delta(s,u)+1\)，由 \(v\) 的选取 \(u.d=\delta(s,u)\)，于是
  \[v.d>\delta(s,v)=\delta(s,u)+1=u.d+1.\tag{22.1}\]
  考虑 \(u\) 出队时 \(v\) 的颜色：白——第 15 行令 \(v.d=u.d+1\)，矛盾；黑——\(v\) 已先出队，由推论 22.4 \(v.d\le u.d\)，矛盾；灰——\(v\) 是在某个比 \(u\) 早出队的 \(w\) 出队时变灰的，\(v.d=w.d+1\le u.d+1\)，矛盾。所有可达顶点必被发现，否则 \(\infty=v.d>\delta(s,v)\)。最后，若 \(v.\pi=u\) 则 \(v.d=u.d+1\)，得到最短路径的构造。

广度优先树。 定义前驱子图 \(G_\pi=(V_\pi,E_\pi)\)：\(V_\pi=\{v\in V:v.\pi\ne\text{NIL}\}\cup\{s\}\)，\(E_\pi=\{(v.\pi,v):v\in V_\pi-\{s\}\}\)。若 \(V_\pi\) 恰为从 \(s\) 可达的顶点，且对每个 \(v\in V_\pi\)，\(G_\pi\) 中从 \(s\) 到 \(v\) 有唯一简单路径且它是 \(G\) 中的最短路径，则 \(G_\pi\) 是广度优先树（连通且 \(|E_\pi|=|V_\pi|-1\)，确实是树）。\(E_\pi\) 中的边称为树边（tree edges）。

• 引理 22.6：BFS 构造的 \(\pi\) 使 \(G_\pi\) 是广度优先树。

打印最短路径（时间与路径上顶点数成线性）：

def PRINT_PATH(G, s, v):
    if v == s:
        print(s)
    elif v.pi is None:
        print("no path from", s, "to", v, "exists")
    else:
        PRINT_PATH(G, s, v.pi)
        print(v)

习题 22.2 概括：22.2-1/22.2-2 手算 BFS；22.2-3 去掉第 18 行（只用 1 位颜色）结果不变；22.2-4 邻接矩阵输入时 BFS 为 \(O(V^2)\)；22.2-5 \(d\) 与邻接表顺序无关但树可能有关；22.2-6 构造某组"最短路径树边"无法由任何顺序的 BFS 产生；22.2-7 摔跤手"好人/坏人"划分（判断二部图并给出 2-着色），\(O(n+r)\)；22.2-8（星号）树的直径：两次 BFS，\(O(V+E)\)；22.2-9 在连通无向图中每条边正反各走一次的路径（以及"用硬币走出迷宫"）。

22.3 深度优先搜索（Depth-first search）（PDF p.624–633）

策略：尽可能"深"地搜索——从最近发现且仍有未探索出边的顶点 \(v\) 出发探索边；\(v\) 的边都探索完后回溯（backtrack）到发现 \(v\) 的顶点。直到发现从原始源点可达的所有顶点；若仍有未发现顶点，选其一为新源点重复，直到发现所有顶点。（BFS 通常限一个源点用于求最短距离，DFS 通常从多个源点出发并作为其他算法的子程序。）

• 前驱 \(v.\pi=u\) 表示 \(v\) 是在扫描 \(u\) 的邻接表时被发现的。DFS 的前驱子图 \(G_\pi=(V,E_\pi)\)，\(E_\pi=\{(v.\pi,v):v\in V,v.\pi\ne\text{NIL}\}\)，构成由若干深度优先树组成的深度优先森林（depth-first forest），\(E_\pi\) 中的边为树边。
• 颜色：初始白，发现时变灰，完成（finished，邻接表已完全检查）时变黑。每个顶点恰属于一棵深度优先树，树互不相交。
• 时间戳（timestamps）：\(v.d\) 记录发现时刻（变灰），\(v.f\) 记录完成时刻（变黑），都是 \(1\) 到 \(2|V|\) 之间的整数，且
  \[u.d<u.f.\tag{22.2}\]
  \(u\) 在 \(u.d\) 前为白，\([u.d,u.f]\) 间为灰，之后为黑。

def DFS(G):
    for u in G.V:
        u.color = WHITE; u.pi = None
    global time; time = 0
    for u in G.V:
        if u.color == WHITE:
            DFS_VISIT(G, u)            # u 成为一棵新深度优先树的根

def DFS_VISIT(G, u):
    global time
    time += 1; u.d = time            # 白顶点 u 刚被发现
    u.color = GRAY
    for v in G.Adj[u]:               # 探索边 (u, v)
        if v.color == WHITE:
            v.pi = u
            DFS_VISIT(G, v)
    u.color = BLACK                  # u 完成
    time += 1; u.f = time

• 图 22.4：在图 22.2 的有向图（顶点 u, v, w, x, y, z）上运行 DFS 的全过程：从 u 出发得 u 1/8、v 2/7、y 3/6、x 4/5，再从 w 出发得 w 9/12、z 10/11；非树边标为 B（后向）、F（前向）、C（横向）。
• 结果依赖 DFS 第 5 行考察顶点的顺序和 DFS-VISIT 第 4 行访问邻居的顺序，但实践中通常任何 DFS 结果都同样可用。

运行时间（聚合分析）：DFS 第 1–3、5–7 行（不计 DFS-VISIT）\(\Theta(V)\)；DFS-VISIT 对每个顶点恰调用一次（调用时顶点必为白，并立即涂灰）；DFS-VISIT(G, v) 的循环执行 \(|Adj[v]|\) 次，\(\sum_v|Adj[v]|=\Theta(E)\)。总时间 \(\Theta(V+E)\)。递归栈空间最坏 \(O(V)\)。

DFS 的性质。

• 前驱子图确实是树构成的森林，其结构恰好反映 DFS-VISIT 的递归调用结构：\(u=v.\pi\) 当且仅当在搜索 \(u\) 的邻接表时调用了 DFS-VISIT(G, v)。\(v\) 是 \(u\) 的后代当且仅当 \(v\) 在 \(u\) 为灰期间被发现。
• 括号结构（parenthesis structure）：用"\((u\)"表示发现 \(u\)，"\(u)\)"表示完成 \(u\)，则发现与完成的历史构成括号正确嵌套的表达式。图 22.5(b)：\((s\,(z\,(y\,(x\ x)\ y)\,(w\ w)\ z)\ s)\ (t\,(v\ v)\,(u\ u)\ t)\)。

定理 22.7（括号定理）：任意 DFS 中，对任意两顶点 \(u,v\)，下列三者恰有一个成立：

• 区间 \([u.d,u.f]\) 与 \([v.d,v.f]\) 完全不相交，且二者在深度优先森林中互不为后代；
• \([u.d,u.f]\) 完全含于 \([v.d,v.f]\)，\(u\) 是 \(v\) 的后代；
• \([v.d,v.f]\) 完全含于 \([u.d,u.f]\)，\(v\) 是 \(u\) 的后代。 证明：设 \(u.d<v.d\)。若 \(v.d<u.f\)，则 \(v\) 在 \(u\) 为灰时被发现，是 \(u\) 的后代，且 \(v\) 比 \(u\) 晚发现，所以在搜索返回并完成 \(u\) 之前 \(v\) 已完成，区间嵌套；若 \(u.f<v.d\)，由 (22.2) 区间不相交，任一个都不是在另一个为灰时被发现的，互不为后代。\(v.d<u.d\) 对称。

推论 22.8（后代区间的嵌套）：\(v\) 是 \(u\) 的真后代当且仅当 \(u.d<v.d<v.f<u.f\)。

定理 22.9（白色路径定理 white-path theorem）：在深度优先森林中，\(v\) 是 \(u\) 的后代当且仅当在发现 \(u\) 的时刻 \(u.d\)，存在一条从 \(u\) 到 \(v\) 的全由白色顶点组成的路径。 证明：⇒：\(v=u\) 时显然；\(v\) 为真后代时由推论 22.8 \(u.d<v.d\)，\(v\) 在 \(u.d\) 时为白，树中 \(u\) 到 \(v\) 路径上的顶点都是 \(u\) 的后代，同理都为白。⇐：设存在白色路径但 \(v\) 未成为 \(u\) 的后代，不妨设路径上其他顶点都成为后代（否则取路径上最靠近 \(u\) 的非后代顶点）。令 \(w\) 为路径上 \(v\) 的前驱（\(w\) 是 \(u\) 的后代，可能 \(w=u\)），由推论 22.8 \(w.f\le u.f\)。\(v\) 必在 \(u\) 被发现后、\(w\) 完成前被发现：\(u.d<v.d<w.f\le u.f\)，由括号定理 \([v.d,v.f]\subset[u.d,u.f]\)，所以 \(v\) 是 \(u\) 的后代，矛盾。

边的分类。 基于 DFS 产生的森林 \(G_\pi\)，边分为四类：

1. 树边（tree edges）：\(G_\pi\) 中的边；\((u,v)\) 是树边当且仅当 \(v\) 是通过探索 \((u,v)\) 首次发现的。
2. 后向边（back edges）：把 \(u\) 连到其在深度优先树中祖先 \(v\) 的边；有向图中的自环也算后向边。
3. 前向边（forward edges）：把 \(u\) 连到其后代 \(v\) 的非树边。
4. 横向边（cross edges）：其他所有边——同一棵树中互不为祖先的顶点之间，或不同树之间。

图 22.5(c) 显示任何图都可重画成树边、前向边朝下，后向边朝上。

DFS 在首次探索边 \((u,v)\) 时可由 \(v\) 的颜色分类：白→树边；灰→后向边（灰顶点总构成与活跃 DFS-VISIT 调用栈对应的一条后代链，探索总从最深的灰顶点出发，所以到达另一灰顶点即到达祖先）；黑→前向边或横向边（\(u.d<v.d\) 为前向边，\(u.d>v.d\) 为横向边，习题 22.3-5）。无向图中 \((u,v)\) 与 \((v,u)\) 是同一条边，按分类表中第一个适用的类型分类，等价于按搜索先遇到哪个方向分类。

定理 22.10：在无向图的 DFS 中，每条边要么是树边，要么是后向边（没有前向边和横向边）。证明：设 \(u.d<v.d\)，\(v\) 在 \(u\) 的邻接表中，所以搜索在 \(u\) 为灰时发现并完成 \(v\)。若首次沿 \(u\to v\) 方向探索，此时 \(v\) 必为白（否则早已沿 \(v\to u\) 探索过），是树边；若首次沿 \(v\to u\) 方向探索，\(u\) 仍为灰，是后向边。

习题 22.3 概括：22.3-1 3×3 颜色表：有向/无向图中从颜色 \(i\) 到颜色 \(j\) 的边可能是哪些类型；22.3-2 在图 22.6（顶点 q–z）上按字母序手算 DFS 并分类；22.3-3 写出图 22.4 的括号结构；22.3-4 去掉 DFS-VISIT 第 8 行（1 位颜色）结果不变；22.3-5 用时间戳刻画四类边：树/前向边 ⟺ \(u.d<v.d<v.f<u.f\)，后向边 ⟺ \(v.d\le u.d<u.f\le v.f\)，横向边 ⟺ \(v.d<v.f<u.d<u.f\)；22.3-6 无向图两种分类方式等价；22.3-7 用栈改写为非递归 DFS；22.3-8/22.3-9 两个关于路径与时间戳的错误猜想的反例；22.3-10 打印每条边及其类型；22.3-11 顶点有入边和出边却单独成树的情形；22.3-12 用 DFS 给无向图连通分量编号 v.cc；22.3-13（星号）判断有向图是否单连通（任意两点间至多一条简单路径）。

22.4 拓扑排序（Topological sort）（PDF p.633–636）

定义。 有向无环图（directed acyclic graph，dag）\(G\) 的拓扑排序是其所有顶点的一个线性次序，使得若 \(G\) 含边 \((u,v)\)，则 \(u\) 在 \(v\) 之前（有环则不存在）。可看作把顶点排在一条水平线上，所有有向边从左指向右。与第 II 部分的"排序"含义不同。

许多应用用 dag 表示事件间的先后约束。图 22.7 例：Bumstead 教授穿衣——内裤→裤子、裤子→鞋、裤子→腰带、衬衫→腰带、衬衫→领带、领带→夹克、腰带→夹克、袜子→鞋；手表独立。DFS 时间戳：内裤 11/16、裤子 12/15、鞋 13/14、衬衫 1/8、领带 2/5、夹克 3/4、腰带 6/7、袜子 17/18、手表 9/10。按完成时间递减得拓扑序：袜子、内裤、裤子、鞋、手表、衬衫、腰带、领带、夹克。

def TOPOLOGICAL_SORT(G):
    order = []                        # 用链表头插
    # 调用 DFS(G) 计算每个顶点的完成时间 v.f
    # 每当一个顶点完成，就把它插入链表头部
    run DFS(G), and when each vertex finishes: order.insert(0, vertex)
    return order                      # 即按 v.f 递减排列

复杂度：DFS \(\Theta(V+E)\)，每个顶点插入链表头 \(O(1)\)，总 \(\Theta(V+E)\)。

引理 22.11：有向图 \(G\) 无环当且仅当对 \(G\) 的 DFS 不产生后向边。证明：⇒（逆否）：若有后向边 \((u,v)\)，\(v\) 是 \(u\) 的祖先，存在 \(v\leadsto u\) 的路径，加上 \((u,v)\) 成环。⇐（逆否）：若 \(G\) 含环 \(c\)，令 \(v\) 是 \(c\) 中第一个被发现的顶点，\((u,v)\) 是 \(c\) 中指向 \(v\) 的边；在 \(v.d\) 时刻，\(c\) 上的顶点构成 \(v\) 到 \(u\) 的白色路径，由白色路径定理 \(u\) 成为 \(v\) 的后代，\((u,v)\) 是后向边。

定理 22.12：TOPOLOGICAL-SORT 对输入 dag 产生拓扑排序。证明：只需证对任意边 \((u,v)\) 有 \(v.f<u.f\)。探索 \((u,v)\) 时 \(v\) 不能是灰色（否则是后向边，与引理 22.11 矛盾）。若 \(v\) 为白，它成为 \(u\) 的后代，\(v.f<u.f\)；若 \(v\) 为黑，\(v\) 已完成，\(v.f\) 已赋值，而 \(u\) 仍在探索中尚未赋 \(u.f\)，所以 \(v.f<u.f\)。

习题 22.4 概括：22.4-1 在图 22.8 的 dag（顶点 m–z）上手算拓扑排序；22.4-2 线性时间统计 dag 中 \(s\) 到 \(t\) 的简单路径数（例：图 22.8 中 p 到 v 恰有 4 条：pov、poryv、posryv、psryv；按拓扑序动态规划）；22.4-3 \(O(V)\) 时间（与 \(|E|\) 无关）判断无向图是否有简单环（DFS 至多看 \(|V|\) 条边就能发现环）；22.4-4 有环时 TOPOLOGICAL-SORT 是否最小化"坏边"数（否）；22.4-5 另一种拓扑排序：反复删除入度为 0 的顶点（Kahn 算法），\(O(V+E)\) 实现，有环时会剩下顶点无法删除。

22.5 强连通分量（Strongly connected components）（PDF p.636–642）

定义。 有向图 \(G=(V,E)\) 的强连通分量（strongly connected component, SCC）是极大顶点集 \(C\subseteq V\)，使得对 \(C\) 中任意 \(u,v\)，同时有 \(u\leadsto v\) 与 \(v\leadsto u\)（互相可达）。许多有向图算法先做 SCC 分解，在每个分量上分别运行，再按分量间连接结构组合结果。

转置图 \(G^{\mathsf T}=(V,E^{\mathsf T})\)，\(E^{\mathsf T}=\{(u,v):(v,u)\in E\}\)；邻接表下构造需 \(O(V+E)\)。\(G\) 与 \(G^{\mathsf T}\) 的 SCC 完全相同。

算法（Kosaraju–Sharir，两次 DFS，\(\Theta(V+E)\)）：

def STRONGLY_CONNECTED_COMPONENTS(G):
    DFS(G)                                  # 1. 计算每个顶点的完成时间 u.f
    GT = transpose(G)                       # 2. O(V+E)
    # 3. 在 GT 上 DFS，但主循环按 u.f 递减的顺序考察顶点
    DFS(GT, vertex_order=sorted(G.V, key=lambda u: u.f, reverse=True))
    # 4. 第 3 步得到的深度优先森林中每棵树的顶点构成一个强连通分量
    return [vertices of each tree in the forest]

分量图（component graph）\(G^{SCC}=(V^{SCC},E^{SCC})\)：设 \(G\) 的 SCC 为 \(C_1,\dots,C_k\)，\(V^{SCC}=\{v_1,\dots,v_k\}\) 每个分量一个顶点；若存在 \(x\in C_i\)、\(y\in C_j\) 使 \((x,y)\in E\)，则 \((v_i,v_j)\in E^{SCC}\)。即把每个分量内部的边收缩成一个点。图 22.9：顶点 a–h 的有向图，SCC 为 {a,b,e}、{c,d}、{f,g}、{h}，分量图为 abe→cd、abe→fg、cd→h、fg→h 等。

关键性质：分量图是 dag。

• 引理 22.13：设 \(C,C'\) 是不同的 SCC，\(u,v\in C\)，\(u',v'\in C'\)，若 \(G\) 中有路径 \(u\leadsto u'\)，则不可能有路径 \(v'\leadsto v\)（否则 \(u\) 与 \(v'\) 互相可达，两分量应合并）。

本节中 \(u.d\)、\(u.f\) 均指第一次 DFS（第 1 行）的时间戳。推广到顶点集：\(d(U)=\min_{u\in U}u.d\)，\(f(U)=\max_{u\in U}u.f\)。

• 引理 22.14：设 \(C,C'\) 是不同 SCC，若存在边 \((u,v)\in E\)，\(u\in C\)、\(v\in C'\)，则 \(f(C)>f(C')\)。证明分两种情况：若 \(d(C)<d(C')\)，令 \(x\) 为 \(C\) 中第一个被发现的顶点，\(x.d\) 时 \(C\cup C'\) 全白，存在从 \(x\) 到它们的白色路径（经 \(x\leadsto u\to v\leadsto w\)），所以它们都成为 \(x\) 的后代，\(x.f=f(C)>f(C')\)。若 \(d(C)>d(C')\)，令 \(y\) 为 \(C'\) 中第一个被发现的顶点，\(C'\) 全部成为 \(y\) 的后代，\(y.f=f(C')\)；由引理 22.13，从 \(C'\) 不能到达 \(C\)，所以 \(y.f\) 时 \(C\) 仍全白，之后才被发现，\(f(C)>f(C')\)。
• 推论 22.15：若 \((u,v)\in E^{\mathsf T}\)，\(u\in C\)、\(v\in C'\)，则 \(f(C)<f(C')\)。即 \(G^{\mathsf T}\) 中跨分量的边总是从完成时间较早的分量指向较晚的分量。

为什么算法正确（直观）：第二次 DFS 在 \(G^{\mathsf T}\) 上从 \(f(C)\) 最大的分量 \(C\) 中某顶点 \(x\) 开始，访问 \(C\) 的所有顶点；由推论 22.15，\(G^{\mathsf T}\) 中没有从 \(C\) 指向其他分量的边，所以不会越界，以 \(x\) 为根的树恰为 \(C\)。然后选剩余分量中 \(f\) 最大的 \(C'\)，它在 \(G^{\mathsf T}\) 中指向其他分量的边只可能指向已访问的 \(C\)……每棵深度优先树恰为一个 SCC。

定理 22.16：STRONGLY-CONNECTED-COMPONENTS 正确计算 SCC。对第 3 行找到的树的个数归纳：设前 \(k\) 棵树都是 SCC，考虑第 \(k+1\) 棵树，根 \(u\) 属于分量 \(C\)，按根的选取方式 \(u.f=f(C)>f(C')\) 对所有尚未访问的其他分量 \(C'\) 成立；访问 \(u\) 时 \(C\) 其余顶点全白，由白色路径定理都成为 \(u\) 的后代；由归纳假设与推论 22.15，\(G^{\mathsf T}\) 中离开 \(C\) 的边只指向已访问分量，所以其他分量的顶点不会成为 \(u\) 的后代。

另一视角：第二次 DFS 按拓扑逆序访问 \((G^{\mathsf T})^{SCC}\) 的顶点；因 \(((G^{\mathsf T})^{SCC})^{\mathsf T}=G^{SCC}\)（习题 22.5-4），也就是按拓扑序访问 \(G^{SCC}\) 的顶点。

复杂度：两次 DFS 加一次转置，\(\Theta(V+E)\) 时间，\(\Theta(V+E)\) 空间（存 \(G^{\mathsf T}\)）。

习题 22.5 概括：22.5-1 加一条新边时 SCC 数如何变化（不变或减少）；22.5-2 在图 22.6 上手算；22.5-3 Bacon 教授的简化（第二次 DFS 用原图并按完成时间递增）是否总正确（否）；22.5-4 证明 \(((G^{\mathsf T})^{SCC})^{\mathsf T}=G^{SCC}\)；22.5-5 \(O(V+E)\) 计算分量图且无重边；22.5-6 构造与 \(G\) 有相同 SCC 与分量图、边数尽可能少的 \(G'\)；22.5-7 判断有向图是否半连通（任意两点至少单向可达；等价于分量图的拓扑序中相邻分量之间都有边，即分量图有哈密顿路径）。

第 22 章思考题（PDF p.642–644）

• 22-1 用 BFS 分类边：(a) 无向图 BFS：无后向边与前向边；树边 \(v.d=u.d+1\)；横向边 \(v.d=u.d\) 或 \(u.d+1\)。(b) 有向图 BFS：无前向边；树边 \(v.d=u.d+1\)；横向边 \(v.d\le u.d+1\)；后向边 \(0\le v.d\le u.d\)。
• 22-2 关节点、桥与双连通分量：连通无向图中，关节点（articulation point）是删除后使图不连通的顶点；桥（bridge）是删除后使图不连通的边；双连通分量（biconnected component）是极大边集，其中任两条边位于同一简单环上。设 \(G_\pi\) 为 DFS 树。(a) 根是关节点 ⟺ 它在 \(G_\pi\) 中至少有两个孩子；(b) 非根 \(v\) 是关节点 ⟺ \(v\) 有某个孩子 \(s\)，使 \(s\) 及其后代都没有指向 \(v\) 的真祖先的后向边；(c) 定义 \(v.low=\min(v.d,\ \{w.d:(u,w)\text{ 是 }v\text{ 的某后代 }u\text{ 的后向边}\})\)，\(O(E)\) 计算；(d) \(O(E)\) 求全部关节点；(e) 边是桥 ⟺ 它不在任何简单环上；(f) \(O(E)\) 求全部桥；(g) 双连通分量划分所有非桥边；(h) \(O(E)\) 给每条边标 e.bcc。（即 Tarjan 的 low-link 方法。）
• 22-3 欧拉回路：强连通有向图的欧拉回路（Euler tour）经过每条边恰一次（顶点可重复）。(a) 存在 ⟺ 每个顶点入度 = 出度；(b) \(O(E)\) 求欧拉回路（合并边不相交的环，Hierholzer 思想）。
• 22-4 可达性：每个顶点有唯一标号 \(L(u)\in\{1..|V|\}\)，\(R(u)\) 为从 \(u\) 可达的顶点集，\(\min(u)\) 为 \(R(u)\) 中标号最小的顶点；\(O(V+E)\) 求所有 \(\min(u)\)（在转置图上按标号从小到大做 DFS/BFS 标记）。

本章注记（PDF p.644）：Even 与 Tarjan 是图算法的优秀参考。BFS 由 Moore 在迷宫寻路中发现，Lee 在电路板布线中独立发现。Hopcroft 与 Tarjan 倡导稀疏图用邻接表，并首先认识到 DFS 的算法重要性；DFS 自 1950 年代末广泛用于人工智能程序。Tarjan 给出线性时间 SCC 算法；22.5 节算法改编自 Aho–Hopcroft–Ullman，归功于 Kosaraju（未发表）与 Sharir；Gabow 给出基于收缩环、用两个栈的线性 SCC 算法。Knuth 首先给出线性时间拓扑排序算法。

第 22 章本章要点

• 表示：邻接表 \(\Theta(V+E)\) 空间适合稀疏图；邻接矩阵 \(\Theta(V^2)\) 适合稠密图与快速查边。
• BFS：FIFO 队列，\(O(V+E)\)，求无权图单源最短距离并构造广度优先树；正确性依赖"队列中 \(d\) 值非降且至多相差 1"。
• DFS：递归/栈，\(\Theta(V+E)\)，产生发现/完成时间戳；括号定理、白色路径定理、四类边（树、后向、前向、横向）；无向图只有树边和后向边。
• 应用：有向图无环 ⟺ DFS 无后向边；拓扑排序 = 按完成时间递减输出；SCC = 在 \(G\) 上 DFS 求完成时间，再在 \(G^{\mathsf T}\) 上按完成时间递减 DFS，每棵树是一个 SCC；分量图是 dag。

与量化交易的关联

• 系统实现：任务依赖与数据管线。因子计算、数据清洗、回测的作业编排（Airflow、Dagster 等调度器）本质上是 dag，执行顺序由拓扑排序给出；用引理 22.11 检测循环依赖。因子之间的依赖（因子 B 由因子 A 派生）也构成 dag，增量重算时只需重算下游。
• 套利与交易图：把货币或交易所资产作为顶点、可兑换关系作为有向边，BFS 可找出最少跳数的兑换路径；SCC 分解可找出彼此可以循环兑换的资产组——只有同一 SCC 内部才可能存在三角套利环（真正检测套利需要第 24 章带负权的 Bellman-Ford）。
• 风险建模/网络分析：在相关性网络、供应链网络、持股关系网络中，连通分量与关节点/桥（思考题 22-2）可用来识别系统性风险的传导关键节点；BFS 距离可衡量冲击传播的层级。
• 数据结构选择：股票相关性网络通常稠密（全连接后按阈值稀疏化），邻接矩阵与 NumPy 矩阵运算天然契合；稀疏的交易关系网络宜用邻接表/CSR 格式。

推荐习题

• 22.1-3、22.1-6（转置图与 \(O(V)\) 通用汇点，矩阵表示的巧用）。
• 22.2-7（二部图判定）、22.2-8（树的直径）。
• 22.3-5（用时间戳刻画边类型）、22.3-7（非递归 DFS，工程实现必备）、22.3-12（DFS 求连通分量）。
• 22.4-2（dag 路径计数，拓扑序上的动态规划）、22.4-5（Kahn 算法）。
• 22.5-3（理解为何必须用转置图）、22.5-5（构造分量图）。
• 思考题 22-2（关节点与桥，Tarjan low 值）、22-3（欧拉回路）。

第 23 章 最小生成树（Minimum Spanning Trees）（PDF p.645–663）

23.0 导言（PDF p.645–646）

动机：电路设计中要把 \(n\) 个引脚连成电气等价，可用 \(n-1\) 根导线两两相连，希望总导线最短。建模为连通无向图 \(G=(V,E)\)：\(V\) 为引脚，\(E\) 为可能的连接，权重 \(w(u,v)\) 为连接代价。求无环子集 \(T\subseteq E\) 连接所有顶点并使

例（图 23.1）：顶点 a–i，边权：a-b 4、a-h 8、b-c 8、b-h 11、c-d 7、c-f 4、c-i 2、d-e 9、d-f 14、e-f 10、f-g 2、g-h 1、g-i 6、h-i 7。一棵 MST 为 {g-h 1, c-i 2, f-g 2, a-b 4, c-f 4, c-d 7, b-c 8, d-e 9}，总权 37。MST 不唯一：去掉 (b,c) 换成 (a,h) 得另一棵权 37 的 MST。

本章两种算法：Kruskal 与 Prim，用二叉堆均可做到 \(O(E\lg V)\)；Prim 用斐波那契堆可达 \(O(E+V\lg V)\)，当 \(|V|\ll|E|\) 时更优。两者都是贪心算法——贪心一般不保证全局最优，但对 MST 可以证明某些贪心策略得到最小权生成树，这是第 16 章理论的经典应用。23.1 给出逐边生长的"通用"方法；23.2 给出两种实现：Kruskal 类似 21.1 节的连通分量算法，Prim 类似 Dijkstra 最短路算法（24.3）。约定树的顶点即其边所关联的顶点。

23.1 最小生成树的生长（Growing a minimum spanning tree）（PDF p.646–651）

通用方法。 维护边集 \(A\)，满足循环不变式：每次迭代前，\(A\) 是某棵最小生成树的子集。 每一步找一条边 \((u,v)\) 使 \(A\cup\{(u,v)\}\) 仍是某棵 MST 的子集，称为 \(A\) 的安全边（safe edge）。

def GENERIC_MST(G, w):
    A = set()
    while A does not form a spanning tree:
        find an edge (u, v) that is safe for A
        A = A | {(u, v)}
    return A

• 初始化：\(A=\varnothing\) 显然满足不变式；保持：只加安全边；终止：\(A\) 中所有边都在某棵 MST 中，返回的 \(A\) 即 MST。
• 安全边一定存在：执行第 3 行时存在 MST \(T\supseteq A\)，且 \(A\) 是 \(T\) 的真子集，\(T\) 中存在不在 \(A\) 中的边，它对 \(A\) 安全。难点在于高效地找到它。

定义。

• 切割（cut）\((S,V-S)\)：\(V\) 的一个划分（图 23.2）。
• 边 \((u,v)\) 横跨（crosses）切割：一个端点在 \(S\)，另一个在 \(V-S\)。
• 切割尊重（respects）边集 \(A\)：\(A\) 中没有边横跨该切割。
• 轻量级边（light edge）：横跨切割的边中权重最小者（可能因平局而不唯一）。更一般地，满足某性质的边中权重最小者称为满足该性质的轻量级边。

定理 23.1（安全边判定）：设 \(G\) 连通无向、权函数实值，\(A\) 包含于某棵 MST，\((S,V-S)\) 是尊重 \(A\) 的任意切割，\((u,v)\) 是横跨该切割的轻量级边，则 \((u,v)\) 对 \(A\) 安全。 证明（剪切粘贴 cut-and-paste）：设 MST \(T\supseteq A\) 且不含 \((u,v)\)（否则已证完）。\((u,v)\) 与 \(T\) 中 \(u\) 到 \(v\) 的简单路径 \(p\) 构成环（图 23.3）。\(u,v\) 在切割两侧，所以 \(p\) 上至少有一条边 \((x,y)\) 横跨切割；切割尊重 \(A\)，故 \((x,y)\notin A\)。删去 \((x,y)\) 把 \(T\) 分成两部分，加入 \((u,v)\) 重新连接，得生成树 \(T'=T-\{(x,y)\}\cup\{(u,v)\}\)。由于 \((u,v)\) 是轻量级边，\(w(u,v)\le w(x,y)\)，

推论观察：算法执行中 \(A\) 始终无环，\(G_A=(V,A)\) 是森林，每个连通分量是一棵树（开始时有 \(|V|\) 棵单顶点树）。任何安全边都连接 \(G_A\) 的不同分量。while 循环恰执行 \(|V|-1\) 次，每次使树的数目减 1，只剩一棵树时终止。

推论 23.2：设 \(A\) 包含于某棵 MST，\(C=(V_C,E_C)\) 是森林 \(G_A\) 中的一个连通分量（树），若 \((u,v)\) 是连接 \(C\) 与 \(G_A\) 中另一分量的轻量级边，则 \((u,v)\) 对 \(A\) 安全。（切割 \((V_C,V-V_C)\) 尊重 \(A\)，\((u,v)\) 是其轻量级边。）

习题 23.1 概括：23.1-1 最小权边属于某棵 MST；23.1-2 定理 23.1 的逆命题（安全边一定是轻量级边）不成立，举反例；23.1-3 若边在某棵 MST 中，则它是某个切割的轻量级边；23.1-4 "是某切割轻量级边的边"的集合不一定构成 MST（如三条等权边的三角形）；23.1-5 环性质：某环上权最大的边 \(e\) 可以删去，\(G-e\) 的某棵 MST 也是 \(G\) 的 MST；23.1-6 若每个切割的轻量级边唯一则 MST 唯一，逆命题不成立；23.1-7 边权全正时，连通所有顶点且总权最小的边集必为树，允许非正权则不然；23.1-8 所有 MST 的边权排序列表相同；23.1-9 MST 在顶点子集上的诱导子图若连通，则是诱导子图的 MST；23.1-10 降低 MST 中某条边的权重后，原树仍是 MST；23.1-11（星号）降低不在 MST 中某条边的权重后，如何更新 MST（加入该边形成环，删去环上最大边，\(O(V)\)）。

23.2 Kruskal 算法与 Prim 算法（The algorithms of Kruskal and Prim）（PDF p.652–659）

两者都细化了通用方法第 3 行选安全边的规则：Kruskal 中 \(A\) 是包含所有顶点的森林，安全边总是连接两个不同分量的最小权边；Prim 中 \(A\) 是一棵树，安全边总是连接该树与树外顶点的最小权边。

Kruskal 算法。 在所有连接森林中两棵不同树的边中，找权重最小的边 \((u,v)\)；设它连接树 \(C_1\) 与 \(C_2\)，它必是连接 \(C_1\) 与其他树的轻量级边，由推论 23.2 对 \(C_1\) 安全。每步都加入可能的最小权边，故为贪心。实现类似 21.1 节连通分量算法，用不相交集合维护每棵树的顶点集：FIND-SET(u) 判断两顶点是否在同一棵树，UNION 合并树。

def MST_KRUSKAL(G, w):
    A = set()
    for v in G.V:
        MAKE_SET(v)
    for (u, v) in sorted(G.E, key=w):      # 按权非降序
        if FIND_SET(u) != FIND_SET(v):     # 两端在不同树中才加入，否则会成环
            A.add((u, v))
            UNION(u, v)
    return A

• 例（图 23.4，对图 23.1 运行）：依次考察 (h,g)1 ✓、(c,i)2 ✓、(g,f)2 ✓、(a,b)4 ✓、(c,f)4 ✓、(i,g)6 ✗（成环）、(c,d)7 ✓、(h,i)7 ✗、(a,h)8 与 (b,c)8 中先考察者 ✓、另一 ✗、(d,e)9 ✓，其余 (e,f)10、(b,h)11、(d,f)14 均 ✗。
• 复杂度（用 21.3 节按秩合并 + 路径压缩的森林）：初始化 \(A\) 为 \(O(1)\)；排序 \(O(E\lg E)\)；\(|V|\) 次 MAKE-SET 与 \(O(E)\) 次 FIND-SET/UNION 共 \(O((V+E)\alpha(V))\)；\(G\) 连通故 \(|E|\ge|V|-1\)，并查集部分为 \(O(E\alpha(V))\)。又 \(\alpha(|V|)=O(\lg V)=O(\lg E)\)，总时间 \(O(E\lg E)\)；因 \(|E|<|V|^2\)，\(\lg|E|=O(\lg V)\)，可写成 \(O(E\lg V)\)。瓶颈在排序。空间 \(O(V+E)\)。

Prim 算法。 与 Dijkstra 算法非常相似。\(A\) 中的边始终构成一棵树：从任意根 \(r\) 出发，每步加入一条把 \(A\) 连到孤立顶点（不与 \(A\) 中任何边关联的顶点）的轻量级边，直到覆盖所有顶点（图 23.5）。由推论 23.2 每步加入的都是安全边。每步加入对树权增加最小的边，故为贪心。

实现关键是快速选新边：所有不在树中的顶点放在以 key 为键的最小优先队列 \(Q\) 中；v.key 是 \(v\) 与树中顶点相连的所有边的最小权重（无此边时为 \(\infty\)）；v.π 是 \(v\) 在树中的父结点。算法隐式维护 \(A=\{(v,v.\pi):v\in V-\{r\}-Q\}\)；结束时 \(Q\) 为空，MST 为 \(A=\{(v,v.\pi):v\in V-\{r\}\}\)。

def MST_PRIM(G, w, r):
    for u in G.V:
        u.key = float('inf'); u.pi = None
    r.key = 0                            # 保证根最先被处理
    Q = MinPriorityQueue(G.V, key=lambda v: v.key)
    while Q:
        u = Q.extract_min()              # u 关联一条横跨切割 (V-Q, Q) 的轻量级边
        for v in G.Adj[u]:
            if v in Q and w(u, v) < v.key:
                v.pi = u
                v.key = w(u, v)          # 隐含一次 DECREASE-KEY

• 三部分循环不变式（while 每次迭代前）：(1) \(A=\{(v,v.\pi):v\in V-\{r\}-Q\}\)；(2) 已放入 MST 的顶点为 \(V-Q\)；(3) 对所有 \(v\in Q\)，若 \(v.\pi\ne\) NIL，则 \(v.key<\infty\) 且 \(v.key\) 是把 \(v\) 连到树中某顶点的轻量级边 \((v,v.\pi)\) 的权重。
• 第 7 行找出关联横跨切割 \((V-Q,Q)\) 的轻量级边的顶点 \(u\)（第一次迭代除外，那时因第 4 行 \(u=r\)）；从 \(Q\) 删去 \(u\) 即把 \((u,u.\pi)\) 加入 \(A\)；第 8–11 行更新与 \(u\) 相邻但不在树中的顶点的 key 与 π，维持不变式第 3 条。
• 例（图 23.5，根 a）：依次加入 (a,b)4；然后 (b,c)8 与 (a,h)8 都是轻量级边，任选其一（图中选 (b,c)）；(c,i)2；(c,f)4；(f,g)2；(g,h)1；(c,d)7；(d,e)9。
• 复杂度：
  • 二叉最小堆：第 1–5 行用 BUILD-MIN-HEAP \(O(V)\)；while 执行 \(|V|\) 次，每次 EXTRACT-MIN \(O(\lg V)\)，共 \(O(V\lg V)\)；for 循环总共执行 \(O(E)\) 次（邻接表总长 \(2|E|\)）；"\(v\in Q\)"用每个顶点一位标志 \(O(1)\) 判断；第 11 行隐含 DECREASE-KEY，二叉堆 \(O(\lg V)\)。总计 \(O(V\lg V+E\lg V)=O(E\lg V)\)，与 Kruskal 渐近相同。
  • 斐波那契堆：EXTRACT-MIN 摊还 \(O(\lg V)\)，DECREASE-KEY 摊还 \(O(1)\)，总计 \(O(E+V\lg V)\)。
  • 邻接矩阵 + 线性扫描找最小 key：\(O(V^2)\)（习题 23.2-2），适合稠密图。
  • 空间 \(O(V+E)\)。

习题 23.2 概括：23.2-1 对每棵 MST \(T\)，都存在一种排序平局打破方式使 Kruskal 返回 \(T\)；23.2-2 邻接矩阵上 \(O(V^2)\) 的 Prim；23.2-3 稀疏图（\(|E|=\Theta(V)\)）上斐波那契堆不比二叉堆渐近更快；稠密图（\(|E|=\Theta(V^2)\)）上更快；一般当 \(|E|=\omega(V)\) 时斐波那契堆实现更快；23.2-4 边权为 \(1..|V|\) 的整数时 Kruskal 可用计数排序做到 \(O(E\alpha(V))\)，边权为 \(1..W\)（常数）时同样；23.2-5 边权为 \(1..|V|\) 时 Prim 可用 vEB 树做到 \(O(E\lg\lg V)\)，为 \(1..W\) 时用桶数组做到 \(O(E)\)；23.2-6（星号）边权在 \([0,1)\) 均匀分布时哪个算法能更快（Kruskal 用桶排序期望线性排序）；23.2-7（星号）已有 MST，加入新顶点及其关联边后如何快速更新（只需在原 MST 边加新边上重算，\(O(V\lg V)\) 或更好）；23.2-8 Borden 教授的分治算法（把顶点分两半递归求 MST 再用最小横跨边连接）是错误的，举反例。

第 23 章思考题（PDF p.659–662）

• 23-1 次优最小生成树（second-best MST）：\(|E|\ge|V|\) 且边权互异。次优 MST 是 \(\min_{T''\ne T'}w(T'')\) 的生成树。(a) 此时 MST 唯一，但次优 MST 不必唯一；(b) 存在 \((u,v)\in T\) 与 \((x,y)\notin T\)，使 \(T-\{(u,v)\}\cup\{(x,y)\}\) 为次优 MST（只需交换一条边）；(c) 对树 \(T\)，\(O(V^2)\) 时间计算所有顶点对之间树上路径的最大权边 \(\max[u,v]\)（从每个顶点 BFS/DFS）；(d) 由此 \(O(V^2)\) 求次优 MST：枚举非树边 \((x,y)\)，代价 \(w(x,y)-w(\max[x,y])\) 最小者。
• 23-2 稀疏图上的最小生成树：预处理减少顶点数。MST-REDUCE：对每个未标记顶点 \(u\) 选其最小权关联边 \((u,v)\) 加入 \(T\)、合并 \(u,v\) 并标记；然后用 FIND-SET 把每条边"改名"为分量对之间的边，多条同名边只保留权最小者（orig 记录原始边，c 记录权）。

def MST_REDUCE(G, T):
    for v in G.V:
        v.mark = False; MAKE_SET(v)
    for u in G.V:
        if not u.mark:
            v = argmin over v in G.Adj[u] of (u, v).c
            UNION(u, v)
            T.add((u, v).orig)
            u.mark = v.mark = True
    G2.V = {FIND_SET(v) for v in G.V}; G2.E = {}
    for (x, y) in G.E:
        u, v = FIND_SET(x), FIND_SET(y)
        if (u, v) not in G2.E:
            G2.E.add((u, v)); (u, v).orig2 = (x, y).orig; (u, v).c2 = (x, y).c
        elif (x, y).c < (u, v).c2:
            (u, v).orig2 = (x, y).orig; (u, v).c2 = (x, y).c
    build adjacency lists G2.Adj
    return G2, T

(a) \(T\) 加上收缩图上 MST 对应的原始边构成 \(G\) 的 MST；(b) \(|G'.V|\le|V|/2\)；(c) 用简单数据结构 \(O(E)\) 实现；(d) \(k\) 个阶段共 \(O(kE)\)；(e) 选 \(k\) 使先做 \(k\) 阶段收缩再跑斐波那契堆 Prim 的总时间为 \(O(E\lg\lg V)\)（取 \(k=\lg\lg V\)），并说明该选择最优；(f) 讨论 \(|E|\) 与 \(|V|\) 满足什么关系时带预处理的 Prim 渐近优于不带预处理的版本（比较 \(O(E\lg\lg V)\) 与 \(O(E+V\lg V)\)，即图足够稀疏、\(|E|=o(V\lg V/\lg\lg V)\) 时）。

• 23-3 瓶颈生成树（bottleneck spanning tree）：最大边权在所有生成树中最小的生成树，其值为最大边权。(a) MST 一定是瓶颈生成树；(b) 线性时间判断瓶颈值是否 ≤ \(b\)（只保留权 ≤ \(b\) 的边，检查连通性）；(c) 结合收缩边的子程序，给出线性时间求瓶颈生成树的算法（对边权中位数二分 + 收缩）。
• 23-4 其他 MST 算法：判断三个算法是否正确并给出最高效实现。(a) MAYBE-MST-A：按权递减考察边，若删去后图仍连通就删去——正确（"反向删除"算法，即环性质的应用）；(b) MAYBE-MST-B：按任意顺序考察边，不成环就加入——不正确，只得到某棵生成树；(c) MAYBE-MST-C：按任意顺序加边，一旦成环就删去环上最大权边——正确（环性质），可用动态树结构高效实现。

本章注记（PDF p.662–663）：Tarjan 有 MST 综述，Graham 与 Hell 整理了 MST 问题的历史。第一个 MST 算法是 Borůvka 1926 年的算法（相当于运行 \(O(\lg V)\) 轮 MST-REDUCE）；Kruskal 1956 年发表；Prim 算法确由 Prim 发明，但 Jarník 1930 年更早提出。贪心有效的根本原因：图的森林集合构成图拟阵（16.4 节）。\(|E|=\Omega(V\lg V)\) 时斐波那契堆 Prim 为 \(O(E)\)；更稀疏的图上 Fredman–Tarjan 结合 Prim、Kruskal、Borůvka 思想与高级数据结构得 \(O(E\lg^*V)\)，Gabow–Galil–Spencer–Tarjan 改进到 \(O(E\lg\lg^*V)\)（PDF 抽取文本中 \(\lg^*\) 的星号丢失，按原书还原）；Chazelle 给出 \(O(E\hat\alpha(E,V))\) 的非贪心算法。相关问题生成树验证：King 给出线性时间算法。以上都是确定性比较模型算法；Karger–Klein–Tarjan 给出期望 \(O(V+E)\) 的随机算法（类似线性时间选择的递归：先找出不可能在 MST 中的边集 \(E'\)，再对 \(E-E'\) 递归）；Fredman–Willard 在 \(b\) 位整数字长模型下给出确定性 \(O(V+E)\) 算法。

第 23 章本章要点

• MST：连通无向带权图中总权最小的生成树，恰 \(|V|-1\) 条边，不一定唯一。
• 核心定理（切割性质）：尊重 \(A\) 的任一切割上的轻量级边对 \(A\) 安全；配套的环性质：环上最大权边可被排除。
• Kruskal：按边权排序 + 并查集，\(O(E\lg V)\)，适合稀疏图、边已排序时更快。Prim：从根生长一棵树 + 最小优先队列，二叉堆 \(O(E\lg V)\)，斐波那契堆 \(O(E+V\lg V)\)，邻接矩阵 \(O(V^2)\) 适合稠密图。
• 贪心正确的深层原因：森林构成图拟阵（第 16 章）。

与量化交易的关联

• 风险建模与资产聚类（直接应用）：Mantegna（1999）提出的"相关性网络/最小生成树"方法是金融网络分析的经典工具：用相关系数 \(\rho_{ij}\) 定义距离 \(d_{ij}=\sqrt{2(1-\rho_{ij})}\)，在 \(N\) 只股票的完全图上求 MST，得到 \(N-1\) 条边的"市场骨架"，可视化行业结构、识别中心股票，并观察危机时期树结构收缩（平均边长变短、中心度集中）。Kruskal 算法按距离从小到大加边的过程与单链接层次聚类（single-linkage）完全等价，MST 切断最长的 \(k-1\) 条边就得到 \(k\) 个聚类。
• 组合优化：López de Prado 的层次风险平价（Hierarchical Risk Parity, HRP）第一步是对相关性距离矩阵做层次聚类（默认单链接，即 MST），再做准对角化和递归二分配权。理解 MST 有助于理解 HRP 的稳定性来源与局限（单链接的"链式效应"）。
• 因子研究：用 MST 或其变体（平面最大过滤图 PMFG）过滤相关矩阵噪声，提取主要依赖结构，用于因子去冗余或构建稀疏协方差估计。
• 实现建议：\(N\) 只股票的完全图有 \(O(N^2)\) 条边，属于稠密图，\(O(V^2)\) 的邻接矩阵版 Prim 最合适；scipy.sparse.csgraph.minimum_spanning_tree 可直接使用。
• 思考题 23-3 的瓶颈生成树对应"使最弱连接最强"的问题，例如在流动性网络中寻找最大化最小流动性的连接结构。

推荐习题

• 23.1-5（环性质）、23.1-6（MST 唯一性条件）、23.1-8（所有 MST 边权多重集相同）、23.1-11（动态更新）。
• 23.2-2（\(O(V^2)\) 矩阵版 Prim，稠密相关矩阵场景直接可用）、23.2-3（堆选择的权衡）、23.2-8（错误的分治，理解切割性质的边界）。
• 思考题 23-1（次优 MST）、23-3（瓶颈生成树）、23-4（反向删除算法）。

第 24 章 单源最短路径（Single-Source Shortest Paths）（PDF p.664–666，仅导言部分）（续见下一块）

24.0 导言（PDF p.664–666）

动机：Patrick 教授想找从 Phoenix 到 Indianapolis 的最短路线。枚举所有路线（即使排除含环路线）数量巨大，且大多不值得考虑（如绕道 Seattle）。本章与第 25 章给出高效方法。

问题定义。 带权有向图 \(G=(V,E)\)，权函数 \(w:E\to\mathbb R\)。路径 \(p=\langle v_0,v_1,\dots,v_k\rangle\) 的权重为其各边权重之和：

问题变体。 本章聚焦单源最短路径问题：给定源点 \(s\)，求 \(s\) 到每个 \(v\in V\) 的最短路径。单源算法可解决：

• 单目的地最短路径：求每个顶点到给定目的地 \(t\) 的最短路径——把所有边反向，化为单源问题。
• 单对顶点最短路径：给定 \(u,v\) 求 \(u\) 到 \(v\) 的最短路径——以 \(u\) 为源解单源问题即可；且已知所有该问题的算法最坏渐近时间都与最好的单源算法相同。
• 所有顶点对最短路径：对每对 \(u,v\) 求最短路径——可从每个顶点各跑一次单源算法，但通常有更快方法，第 25 章专门讨论。

最短路径的最优子结构。 最短路径算法通常依赖"最短路径包含其他最短路径"的性质（第 26 章 Edmonds-Karp 最大流也依赖它）。最优子结构是动态规划（第 15 章）与贪心（第 16 章）可能适用的标志：Dijkstra 算法（24.3）是贪心算法，Floyd-Warshall 算法（25.2）是动态规划算法。

引理 24.1（最短路径的子路径也是最短路径）：设 \(p=\langle v_0,v_1,\dots,v_k\rangle\) 是 \(v_0\) 到 \(v_k\) 的最短路径，对任意 \(0\le i\le j\le k\)，子路径 \(p_{ij}=\langle v_i,\dots,v_j\rangle\) 是 \(v_i\) 到 \(v_j\) 的最短路径。 证明：把 \(p\) 分解为 \(v_0\overset{p_{0i}}{\leadsto}v_i\overset{p_{ij}}{\leadsto}v_j\overset{p_{jk}}{\leadsto}v_k\)，\(w(p)=w(p_{0i})+w(p_{ij})+w(p_{jk})\)。若存在 \(w(p'_{ij})<w(p_{ij})\) 的路径 \(p'_{ij}\)，则 \(v_0\overset{p_{0i}}{\leadsto}v_i\overset{p'_{ij}}{\leadsto}v_j\overset{p_{jk}}{\leadsto}v_k\) 的权重小于 \(w(p)\)，与 \(p\) 最短矛盾（剪切粘贴论证）。

负权边。 单源最短路问题的某些实例可能含负权边。

• 若 \(G\) 不含从源点 \(s\) 可达的负权环（negative-weight cycle），则对所有 \(v\)，\(\delta(s,v)\) 仍有良好定义（可以为负）。
• 若含从 \(s\) 可达的负权环，最短路径权重无良好定义：到环上任一顶点的路径都可以沿负权环多绕几圈得到更小权重。若 \(s\) 到 \(v\) 的某条路径上有负权环，定义 \(\delta(s,v)=-\infty\)。

例（图 24.1）：

• \(s\to a\) 只有一条路径，\(\delta(s,a)=w(s,a)=3\)；\(s\to b\) 也只有一条，\(\delta(s,b)=w(s,a)+w(a,b)=3+(-4)=-1\)。
• \(s\) 到 \(c\) 有无穷多条路径：\(\langle s,c\rangle\)、\(\langle s,c,d,c\rangle\)、……；环 \(\langle c,d,c\rangle\) 权重 \(6+(-3)=3>0\)，所以最短路径为 \(\langle s,c\rangle\)，\(\delta(s,c)=w(s,c)=5\)；同理 \(\delta(s,d)=w(s,c)+w(c,d)=11\)。
• \(s\) 到 \(e\)：环 \(\langle e,f,e\rangle\) 权重 \(3+(-6)=-3<0\)，可绕任意多圈得到任意小的权重，没有最短路径，\(\delta(s,e)=-\infty\)；同理 \(\delta(s,f)=-\infty\)；\(g\) 可从 \(f\) 到达，\(\delta(s,g)=-\infty\)。
• 顶点 \(h,i,j\) 也构成负权环，但从 \(s\) 不可达，所以 \(\delta(s,h)=\delta(s,i)=\delta(s,j)=\infty\)。

（本块到此结束；第 24 章其余部分——负权环的进一步讨论、环、最短路径的表示、松弛操作、Bellman-Ford、DAG 最短路、Dijkstra、差分约束、最短路径性质的证明——见下一块。）

与量化交易的关联（第 24 章导言部分）

• 最短路径的"路径权重 = 边权之和"框架可直接用于汇率套利检测：令边权 \(w(u,v)=-\ln r_{uv}\)（\(r_{uv}\) 为 \(u\) 兑 \(v\) 的汇率），则一个兑换环的总收益 \(\prod r>1\) 当且仅当 \(\sum w<0\)，即存在负权环。本节对负权环使最短路无定义的讨论，正是后续 Bellman-Ford 算法检测套利机会的理论基础（该算法在下一块）。
• 边权可表示成本、时间、风险等任何沿路径线性累加的量，例如多市场转运/调仓路径上的累计交易成本最小化。

推荐习题（第 24 章导言部分）

• 本块未包含第 24 章的习题（习题在下一块）。建议结合引理 24.1 思考：带负权但无负环时子路径最优性仍成立，而"最长简单路径"问题则不具有这种最优子结构（参见第 15 章讨论）。