第十三讲 Union Find

并查集（Union-Find）

合并：指定两个元素，将这两个元素所在的集合合并
查找：查找指定元素所处集合的代表元

利用链表完成并查集

用链表联系起一个集合中的所有元素
头指针中的元素是此集合的代表
每一个元素都储存有一个指针（Leader pointer）指向代表
查找操作时间复杂度为$O(1)$
合并操作时间复杂度为$O(n)$，可优化为仅改变较小长度链表，时间复杂度为$\min\{L(x),L(y)\}$。

一个元素在整个过程中，其 Leader 指针最多会被修改多少次？

一个元素的集合大小从 1 开始，每次修改指针后所处集合大小至少翻两倍，次数 $m$ 满足 $2^m \le n$，因此 $m \le \log_2 n$。即任意一个元素的指针在整个生命周期内，最多只会被修改 $O(\log n)$ 次。有 $n$ 个元素，每个元素最多贡献 $\log n$ 次修改，所有合并操作的总复杂度是 $O(n \log n)$。均摊运行时间为$O(\log n)$。

势能分析法

每个元素 $x$ 的势函数：$\phi(x) = \lg n - \lg |L(x)|$，$n$ 是总元素个数。$|L(x)|$ 是元素 $x$ 当前所属集合（链表）的大小。

直观理解： 当元素处于小集合时，势能很高；集合变大时，其势能会降低。

总势能 $\Phi$ 是所有元素势能的总和：$\Phi = \sum \phi(x)$。

初始状态：$\phi(x) = \lg n$。初始总势能：$\Phi_{initial} = n \lg n$。

执行合并操作，假设 $L(x)$ 是较短的链表，实际代价正比于短链表长度 $O(|L(x)|)$。当 $L(x)$ 合并到 $L(y)$ 时，新集合的大小变为 $|L(x)| + |L(y)|$。

对于原 $L(y)$ 中的元素，它们的集合大小变大了，势能下降，我们忽略这一部分。
对于 $L(x)$ 中的任意元素$z$，其势能变化量为： $$\Delta \phi(z) =\displaystyle \lg \frac{|L(x)|}{|L(x)| + |L(y)|}$$，又 $|L(x)| + |L(y)| \ge 2|L(x)|$。
则$\displaystyle \Delta \phi(z) \le \lg(\frac{1}{2}) = -1$。每一个受影响的元素，势能至少降低了 1。
对于 $L(x)$ 中所有 $|L(x)|$ 个元素，总势能变化量 $\Delta \Phi \le -|L(x)|$。

计算摊还代价的公式为： $$\text{摊还代价} = \text{实际代价} + \text{势能变化量} (\Delta \Phi)$$ 根据上述推导，实际代价 $\approx |L(x)|$，势能变化量 $\Delta \Phi \le -|L(x)|$，$\text{摊还代价} \le = 0$。

利用有根树完成并查集

在链表背景下，进行合并操作时我们修改较短链表上所有元素的leader pointer，现在我们只修改其代表元素的指针，使其指向另一集合的代表元素。

此时合并与查找的操作取决于待合并元素到根路径长度之和。

类比加短并长思想，合并时将树高较小的合并到树高较大的树中。只有当一个节点所在的子树与另一个等大或更大的子树合并时，该节点到根的距离才会增加。这意味着子树规模至少翻倍。树的高度（即路径长度）被限制在 $O(\log n)$。

优化：在执行查找的过程中，既然已经走了一遍从$z$到根节点的长路径，可顺手把这条路径上所有的节点都直接指向根节点。一旦执行过一次深层的查找，该路径上的所有元素下次执行查找时都将是 $O(1)$。

为保证树不退化成链表，需要一套规则来决定合并时的“方向”。

秩（Rank）： 每个节点的属性，在没有路径压缩的情况下，Rank是树高
合并规则：
1. 秩小并入秩大： Rank较小的树根指向Rank较大的树根。整棵树的秩不增
2. 等秩合并： 当两树Rank相等时，合并后新根节点的Rank加 1。
定义： 当 $x$ 是 $y$ 的父节点时，通常有 $\text{rank}(x) > \text{rank}(y)$。
单独使用按秩合并： 保证了树的高度永远不会超过 $\lfloor \lg n \rfloor$。因此 Find 和 Union 的最坏情况复杂度都是 $O(\log n)$。

利用数学归纳法：转证：当高度为$h$时，树结点个数大于$2^h$，使用数学归纳法，只有当树高均为$h-1$时进行合并操作才会增加树高为$h$。

单独使用路径压缩： 在 $m$ 次操作中，最坏情况复杂度是 $O(n + m \log_{1+m/n} n)$。
按秩合并 + 路径压缩： 这是算法史上最著名的结论之一。经过证明，同时使用这两种优化时，并查集每步操作的均摊时间复杂度为： $$O(\alpha(n))$$，这里的 $\alpha(n)$ 是 反阿克曼函数。

标准并查集操作（Tarjan，1975）

数据结构

p(x) (Parent Pointer)：每个节点 x 存储一个指针指向其父节点。
rank(x) (Rank)：该节点的秩。

查找操作

检查 x 是否为根节点。是则直接返回 x。
p(x) = Find(p(x))。这一递归调用会一路向上查找根节点。在返回的过程中，它会将路径上遇到的所有节点，直接连接到根节点下（路径压缩）。

合并操作

找到 x 和 y 各自的根节点 s 和 t。
如果 s 的秩大于 t，直接把 t 接到 s 下面。
如果秩相等，所以任选一个作为新根（s），将 s 秩加 1， t 接到 s 下面。

并查集算法的时间复杂度分析

核心变量 $\Delta_1(x)$：定义为父节点与当前节点“秩”的差。 $$\Delta_1(x) = \text{rank}(p(x)) - \text{rank}(x)$$
势函数 $\phi(x)$ 的设计：
- 对于非根节点，$\phi(x) = \lg n - \lfloor \lg \Delta_1(x) \rfloor$。当路径被压缩时，某个节点 $x$ 会被直接挂到很远处的根节点下。这意味着它的父节点的秩 $\text{rank}(p(x))$ 会剧增，导致 $\Delta_1(x)$ 变大。
- 此时$\phi(x)$ 会减小。这种释放出来的势能用来支付路径压缩时遍历节点的实际耗时。
- 对于根节点，$\phi(x)=\lg n\cdot \rank(x)$

在长为 $L$ 的查找路径上，我们可以把节点按照 $\lfloor \lg \Delta_1(x) \rfloor$ 的值（记为 $k$）进行分类。由于 $\text{rank}$ 的取值范围在 $[0, \lg n]$ 之间，所以 $k$ 的可能取值非常少（只有 $\lg(\lg n)$ 级别）。直观上认为，一条长路径上的大部分节点 $x$ 都会和它的某个祖先 $y$ 拥有相同的 $k$ 值。

如果存在元素$x$及其祖先$y$满足$\lfloor \lg\Delta_1(y)\rfloor=\lfloor \lg\Delta_1(x)\rfloor=k$

则$\rank(root)-\rank(x)\ge \Delta_1(y)+\Delta_1(x)\ge 2^{k+1}$

当路径压缩完成后。这导致 $x$ 的 $k$ 值至少增加 1，对应势能 $\phi(x)$ 至少下降 1。

Claim：对一条长度为$L$的路径压缩，这一原则对$L-\log \log n$个元素适用。故总势能减小$\ge L-\log\log n$

优化变量 $\Delta_2(x)$：改为使用比率 $\frac{\text{rank}(p(x))}{\text{rank}(x)}$，而不再是差值。

如果存在元素$x$及其祖先$y$满足$\lfloor \lg\Delta_2(y)\rfloor=\lfloor \lg\Delta_2(x)\rfloor=k$

则$\displaystyle \frac{rank(root)}{\rank(x)}\ge \Delta_2(y)\Delta_2(x)\ge 2^{2^{k+1}}$

当路径压缩完成后。这导致 $x$ 的 $k$ 值至少增加 1，对应势能 $\phi(x)$ 至少下降 1。

Claim：对一条长度为$L$的路径压缩，这一原则对$L-\log \log\log n$个元素适用。故总势能减小$\ge L-\log \log \log n$

我们更进一步，使用迭代对数级差并修改势能函数$\Delta_3(x)=\max\{k|\lg^{(k)}[(\rank(p(x))]\ge \rank(x)\}$

$\phi(x)=\begin{cases}\lg \lg ^*n\cdot \rank(x)& root\\ \lg \lg ^* n-\lfloor\lg \Delta_3(x)\rfloor & else\end{cases}$

迭代对数 $\lg^* n$ ，$\lg^{(k)} n$ 表示对 $n$ 连续取 $k$ 次对数。

如果 $n = 2^{65536}$，$\lg^* n$ 也仅为 $5$。在现实世界的计算中，可以粗略地认为 $\lg^* n$ 是一个常数。
$\Delta_3(x)$衡量的是父节点的秩相对于当前节点的秩，在“对数嵌套深度”上领先了多少。

Claim：$0\le \Delta_3(x)\le \lg^* n=\min\{k|\lg ^{(k)}n<0\}$

如果存在元素$x$及其祖先$y$满足$\lfloor \lg\Delta_3(y)\rfloor=\lfloor \lg\Delta_3(x)\rfloor=k$

则$\displaystyle \lg^{2^{k+1}}(\rank(r))\ge \lg^{2^k}(\rank(y))\ge \rank(x)$

因此$\phi(x)$将减少1

Claim：对一条长度为$L$的路径压缩，这一原则对$L-\log \log\log n$个元素适用。故总势能减小$\ge L-\log \lg^*n$

阿克曼函数 (Ackermann Function) （期中不考）

$A_k(j)=\begin{cases}j+1 & k=0\\ A_{k-1}^{(j+1)}(j) & k>0\end{cases}$

$A_0(j)$：简单的加法（线性）。
$A_1(j)$：迭代加法 $\rightarrow$ 变成乘法 ($2j + 1$)。
$A_2(j)$：迭代乘法 $\rightarrow$ 变成幂运算（指数级，$2^{j+1}(j+1)-1$）。
$A_3(j)$：迭代幂运算 $\rightarrow$ 变成叠幂运算，即 $2^{2^{2^{\dots^{2}}}}$，高度为 $j$。
$A_4(j)$：增长速度已经超越了人类感官的理解，在 $j$ 很小时结果就超过了宇宙中原子的总数。

并查集的均摊时间复杂度 $O(\alpha(n))$，即阿克曼函数的反函数。

通过 $\Delta_1, \Delta_2, \Delta_3$ 不断重定义势函数。每一层定义实际上都在利用更深层次的对数嵌套，本质是在寻找：究竟需要迭代多少层对数，才能让路径上几乎所有节点的势能下降都能覆盖其代价？这个嵌套的层数正是阿克曼函数的反函数 $\alpha(n)$。

阿克曼函数 ($A_k$) 的引入：为了量化极其剧烈的增长，引入了阿克曼函数。即使 $k=4$，$A_4(n)$ 的值也是一个“天文数字”。
直观理解：在路径压缩中，父节点会不断向上跳跃，导致 $\text{rank}(p(x))$ 远大于 $\text{rank}(x)$。我们通过寻找一个 $k$ 值，使得 $\text{rank}(p(x)) \approx A_k(\text{rank}(x))$，以此来反映这种“跨度”。
反阿克曼函数 $\alpha(n)$：定义为使得 $A_k(1) > n$ 的最小 $k$ 值。由于阿克曼函数增长极快，$\alpha(n)$ 在宇宙可观测范围内通常不大于 5。
层级 $\text{level}(x)$：衡量父节点秩领先节点秩的“数量级”。它是最大的 $k$，满足 $\text{rank}(p(x)) \ge A_k(\text{rank}(x))$。
迭代次数 $\text{iter}(x)$：在当前的层级 $k$ 下，衡量还差多少次迭代能进入下一个层级。
取值范围：证明了 $1 \le \text{iter}(x) \le \text{rank}(x)$，以及 $\text{level}(x) < \alpha(n)$。

使用势能分析法，每个节点被赋予一个势能值 $\phi(x)$： * 根节点：势能较高，为 $\alpha(n) \cdot \text{rank}(x)$。 * 非根节点：$\phi(x) = (\alpha(n) - \text{level}(x)) \cdot \text{rank}(x) - \text{iter}(x)$。 * 直观意义： * 当 $\text{level}(x)$ 增加时（即父节点秩跨度变大），势能 $\phi(x)$ 会显著下降。 * 当 $\text{iter}(x)$ 增加时，势能也会微弱下降。 * 路径压缩的操作会消耗这些势能，从而抵消实际的操作耗时。

单次查找操作中，路径上大部分节点的势能都会至少减少 1。如果路径上存在一个祖先 $y$，使得 $y$ 和 $x$ 处于相同的层级（$\text{level}(x) = \text{level}(y)$）。除了路径上靠近根部的少数几个节点（约 $\alpha(n)$ 个）外，其余每个节点在路径压缩后势能都会减 1。