跳转至

# 并查集复杂度

本部分内容转载并修改自 时间复杂度 - 势能分析浅谈，已取得原作者授权同意．

## 定义

### 阿克曼函数

这里，先给出 𝛼(𝑛)α(n) 的定义．为了给出这个定义，先给出 𝐴 𝑘(𝑗)A k(j) 的定义．

定义 𝐴 𝑘(𝑗)A k(j) 为：

𝐴 𝑘(𝑗)={𝑗+1 𝑘=0 𝐴(𝑗+1)𝑘−1(𝑗)𝑘≥1 A k(j)={j+1 k=0 A k−1(j+1)(j)k≥1

即阿克曼函数．

这里，𝑓 𝑖(𝑥)f i(x) 表示将 𝑓 f 连续应用在 𝑥 x 上 𝑖 i 次，即 𝑓 0(𝑥) =𝑥 f 0(x)=x，𝑓 𝑖(𝑥) =𝑓(𝑓 𝑖−1(𝑥))f i(x)=f(f i−1(x))．

再定义 𝛼(𝑛)α(n) 为使得 𝐴 𝛼(𝑛)(1) ≥𝑛 A α(n)(1)≥n 的最小整数值．注意，我们之前将它描述为 𝐴 𝛼(𝑛)(𝛼(𝑛)) ≥𝑛 A α(n)(α(n))≥n，反正他们的增长速度都很慢，值都不超过 4．

### 基础定义

每个节点都有一个 rank．这里的 rank 不是节点个数，而是深度．节点的初始 rank 为 0，在合并的时候，如果两个节点的 rank 不同，则将 rank 小的节点合并到 rank 大的节点上，并且不更新大节点的 rank 值．否则，随机将某个节点合并到另外一个节点上，将根节点的 rank 值 +1．这里根节点的 rank 给出了该树的高度．记 x 的 rank 为 𝑟 𝑛 𝑘(𝑥)r n k(x)，类似的，记 x 的父节点为 𝑓 𝑎(𝑥)f a(x)．我们总有 𝑟 𝑛 𝑘(𝑥) +1 ≤𝑟 𝑛 𝑘(𝑓 𝑎(𝑥))r n k(x)+1≤r n k(f a(x))．

为了定义势函数，需要预先定义一个辅助函数 𝑙 𝑒 𝑣 𝑒 𝑙(𝑥)l e v e l(x)．其中，𝑙 𝑒 𝑣 𝑒 𝑙(𝑥) =m a x(𝑘 :𝑟 𝑛 𝑘(𝑓 𝑎(𝑥)) ≥𝐴 𝑘(𝑟 𝑛 𝑘(𝑥)))l e v e l(x)=max(k:r n k(f a(x))≥A k(r n k(x)))．当 𝑟 𝑛 𝑘(𝑥) ≥1 r n k(x)≥1 的时候，再定义一个辅助函数 𝑖 𝑡 𝑒 𝑟(𝑥) =m a x(𝑖 :𝑟 𝑛 𝑘(𝑓 𝑎(𝑥)) ≥𝐴 𝑖 𝑙 𝑒 𝑣 𝑒 𝑙(𝑥)(𝑟 𝑛 𝑘(𝑥))i t e r(x)=max(i:r n k(f a(x))≥A l e v e l(x)i(r n k(x))．这些函数定义的 𝑥 x 都满足 𝑟 𝑛 𝑘(𝑥) >0 r n k(x)>0 且 𝑥 x 不是某个树的根．

上面那些定义可能让你有点头晕．再理一下，对于一个 𝑥 x 和 𝑓 𝑎(𝑥)f a(x)，如果 𝑟 𝑛 𝑘(𝑥) >0 r n k(x)>0，总是可以找到一对 𝑖,𝑘 i,k 令 𝑟 𝑛 𝑘(𝑓 𝑎(𝑥)) ≥𝐴 𝑖 𝑘(𝑟 𝑛 𝑘(𝑥))r n k(f a(x))≥A k i(r n k(x))，而 𝑙 𝑒 𝑣 𝑒 𝑙(𝑥) =m a x(𝑘)l e v e l(x)=max(k)，在这个前提下，𝑖 𝑡 𝑒 𝑟(𝑥) =m a x(𝑖)i t e r(x)=max(i)．𝑙 𝑒 𝑣 𝑒 𝑙 l e v e l 描述了 𝐴 A 的最大迭代级数，而 𝑖 𝑡 𝑒 𝑟 i t e r 描述了在最大迭代级数时的最大迭代次数．

对于这两个函数，𝑙 𝑒 𝑣 𝑒 𝑙(𝑥)l e v e l(x) 总是随着操作的进行而增加或不变，如果 𝑙 𝑒 𝑣 𝑒 𝑙(𝑥)l e v e l(x) 不增加，𝑖 𝑡 𝑒 𝑟(𝑥)i t e r(x) 也只会增加或不变．并且，它们总是满足以下两个不等式：

0≤𝑙 𝑒 𝑣 𝑒 𝑙(𝑥)<𝛼(𝑛)0≤l e v e l(x)<α(n)1≤𝑖 𝑡 𝑒 𝑟(𝑥)≤𝑟 𝑛 𝑘(𝑥)1≤i t e r(x)≤r n k(x)

考虑 𝑙 𝑒 𝑣 𝑒 𝑙(𝑥)l e v e l(x)、𝑖 𝑡 𝑒 𝑟(𝑥)i t e r(x) 和 𝐴 𝑗 𝑘 A k j 的定义，这些很容易被证明出来，就留给读者用于熟悉定义了．

定义势能函数 Φ(𝑆) =∑𝑥∈𝑆 Φ(𝑥)Φ(S)=∑x∈S Φ(x)，其中 𝑆 S 表示一整个并查集，而 𝑥 x 为并查集中的一个节点．定义 Φ(𝑥)Φ(x) 为：

Φ(𝑥)={𝛼(𝑛)×r n k(𝑥)r n k(𝑥)=0 或 𝑥 为某棵树的根节点(𝛼(𝑛)−l e v e l(𝑥))×r n k(𝑥)−𝑖 𝑡 𝑒 𝑟(𝑥)o t h e r w i s e Φ(x)={α(n)×rnk(x)rnk(x)=0 或 x 为某棵树的根节点(α(n)−level(x))×rnk(x)−i t e r(x)otherwise

然后就是通过操作引起的势能变化来证明摊还时间复杂度为 Θ(𝛼(𝑛))Θ(α(n)) 啦．注意，这里我们讨论的 𝑢 𝑛 𝑖 𝑜 𝑛(𝑥,𝑦)u n i o n(x,y) 操作保证了 𝑥 x 和 𝑦 y 都是某个树的根，因此不需要额外执行 𝑓 𝑖 𝑛 𝑑(𝑥)f i n d(x) 和 𝑓 𝑖 𝑛 𝑑(𝑦)f i n d(y)．

可以发现，势能总是个非负数．另，在开始的时候，并查集的势能为 0 0．

## 证明

### union(x,y) 操作

其花费的时间为 Θ(1)Θ(1)，因此我们考虑其引起的势能的变化．

这里，我们假设 𝑟 𝑛 𝑘(𝑥) ≤𝑟 𝑛 𝑘(𝑦)r n k(x)≤r n k(y)，即 𝑥 x 被接到 𝑦 y 上．这样，势能增加的节点仅有 𝑥 x（从树根变成非树根），𝑦 y（秩可能增加）和操作前 𝑦 y 的子节点（父节点的秩可能增加）．我们先证明操作前 𝑦 y 的子节点 𝑐 c 的势能不可能增加，并且如果减少了，至少减少 1 1．

设操作前 𝑐 c 的势能为 Φ(𝑐)Φ(c)，操作后为 Φ(𝑐′)Φ(c′)，这里 𝑐 c 可以是任意一个 𝑟 𝑛 𝑘(𝑐) >0 r n k(c)>0 的非根节点，操作可以是任意操作，包括下面的 find 操作．我们分三种情况讨论．

1. 𝑖 𝑡 𝑒 𝑟(𝑐)i t e r(c) 和 𝑙 𝑒 𝑣 𝑒 𝑙(𝑐)l e v e l(c) 并未增加．显然有 Φ(𝑐) =Φ(𝑐′)Φ(c)=Φ(c′)．
2. 𝑖 𝑡 𝑒 𝑟(𝑐)i t e r(c) 增加了，𝑙 𝑒 𝑣 𝑒 𝑙(𝑐)l e v e l(c) 并未增加．这里 𝑖 𝑡 𝑒 𝑟(𝑐)i t e r(c) 至少增加一，即 Φ(𝑐′) ≤Φ(𝑐) −1 Φ(c′)≤Φ(c)−1，势能函数减少了，并且至少减少 1．
3. 𝑙 𝑒 𝑣 𝑒 𝑙(𝑐)l e v e l(c) 增加了，𝑖 𝑡 𝑒 𝑟(𝑐)i t e r(c) 可能减少．但是由于 0 <𝑖 𝑡 𝑒 𝑟(𝑐) ≤𝑟 𝑛 𝑘(𝑐)0<i t e r(c)≤r n k(c)，𝑖 𝑡 𝑒 𝑟(𝑐)i t e r(c) 最多减少 𝑟 𝑛 𝑘(𝑐) −1 r n k(c)−1，而 𝑙 𝑒 𝑣 𝑒 𝑙(𝑐)l e v e l(c) 至少增加 1 1．由定义 Φ(𝑐) =(𝛼(𝑛) −𝑙 𝑒 𝑣 𝑒 𝑙(𝑐)) ×𝑟 𝑛 𝑘(𝑐) −𝑖 𝑡 𝑒 𝑟(𝑐)Φ(c)=(α(n)−l e v e l(c))×r n k(c)−i t e r(c)，可得 Φ(𝑐′) ≤Φ(𝑐) −1 Φ(c′)≤Φ(c)−1．
4. 其他情况．由于 𝑟 𝑛 𝑘(𝑐)r n k(c) 不变，𝑟 𝑛 𝑘(𝑓 𝑎(𝑐))r n k(f a(c)) 不减，所以不存在．

所以，势能增加的节点仅可能是 𝑥 x 或 𝑦 y．而 𝑥 x 从树根变成了非树根，如果 𝑟 𝑛 𝑘(𝑥) =0 r n k(x)=0，则一直有 Φ(𝑥) =Φ(𝑥′) =0 Φ(x)=Φ(x′)=0．否则，一定有 𝛼(𝑥) ×𝑟 𝑛 𝑘(𝑥) ≥(𝛼(𝑛) −𝑙 𝑒 𝑣 𝑒 𝑙(𝑥)) ×𝑟 𝑛 𝑘(𝑥) −𝑖 𝑡 𝑒 𝑟(𝑥)α(x)×r n k(x)≥(α(n)−l e v e l(x))×r n k(x)−i t e r(x)．即，Φ(𝑥′) ≤Φ(𝑥)Φ(x′)≤Φ(x)．

因此，唯一势能可能增加的点就是 𝑦 y．而 𝑦 y 的势能最多增加 𝛼(𝑛)α(n)．因此，可得 𝑢 𝑛 𝑖 𝑜 𝑛 u n i o n 操作均摊后的时间复杂度为 Θ(𝛼(𝑛))Θ(α(n))．

### find(a) 操作

如果查找路径包含 Θ(𝑠)Θ(s) 个节点，显然其查找的时间复杂度是 Θ(𝑠)Θ(s)．如果由于查找操作，没有节点的势能增加，且至少有 𝑠 −𝛼(𝑛)s−α(n) 个节点的势能至少减少 1 1，就可以证明 𝑓 𝑖 𝑛 𝑑(𝑎)f i n d(a) 操作的时间复杂度为 Θ(𝛼(𝑛))Θ(α(n))．为了避免混淆，这里用 𝑎 a 作为参数，而出现的 𝑥 x 都是泛指某一个并查集内的结点．

首先证明没有节点的势能增加．很显然，我们在上面证明过所有非根节点的势能不增，而根节点的 𝑟 𝑛 𝑘 r n k 没有改变，所以没有节点的势能增加．

接下来证明至少有 𝑠 −𝛼(𝑛)s−α(n) 个节点的势能至少减少 1 1．我们上面证明过了，如果 𝑙 𝑒 𝑣 𝑒 𝑙(𝑥)l e v e l(x) 或者 𝑖 𝑡 𝑒 𝑟(𝑥)i t e r(x) 有改变的话，它们的势能至少减少 1 1．所以，只需要证明至少有 𝑠 −𝛼(𝑛)s−α(n) 个节点的 𝑙 𝑒 𝑣 𝑒 𝑙(𝑥)l e v e l(x) 或者 𝑖 𝑡 𝑒 𝑟(𝑥)i t e r(x) 有改变即可．

回忆一下非根节点势能的定义，Φ(𝑥) =(𝛼(𝑛) −𝑙 𝑒 𝑣 𝑒 𝑙(𝑥)) ×𝑟 𝑛 𝑘(𝑥) −𝑖 𝑡 𝑒 𝑟(𝑥)Φ(x)=(α(n)−l e v e l(x))×r n k(x)−i t e r(x)，而 𝑙 𝑒 𝑣 𝑒 𝑙(𝑥)l e v e l(x) 和 𝑖 𝑡 𝑒 𝑟(𝑥)i t e r(x) 是使 𝑟 𝑛 𝑘(𝑓 𝑎(𝑥)) ≥𝐴 𝑖 𝑡 𝑒 𝑟(𝑥)𝑙 𝑒 𝑣 𝑒 𝑙(𝑥)(𝑟 𝑛 𝑘(𝑥))r n k(f a(x))≥A l e v e l(x)i t e r(x)(r n k(x)) 的最大数．

所以，如果 𝑟 𝑜 𝑜 𝑡 𝑥 r o o t x 代表 𝑥 x 所处的树的根节点，只需要证明 𝑟 𝑛 𝑘(𝑟 𝑜 𝑜 𝑡 𝑥) ≥𝐴 𝑖 𝑡 𝑒 𝑟(𝑥)+1 𝑙 𝑒 𝑣 𝑒 𝑙(𝑥)(𝑟 𝑛 𝑘(𝑥))r n k(r o o t x)≥A l e v e l(x)i t e r(x)+1(r n k(x)) 就好了．根据 𝐴 𝑖 𝑘 A k i 的定义，𝐴 𝑖 𝑡 𝑒 𝑟(𝑥)+1 𝑙 𝑒 𝑣 𝑒 𝑙(𝑥)(𝑟 𝑛 𝑘(𝑥)) =𝐴 𝑙 𝑒 𝑣 𝑒 𝑙(𝑥)(𝐴 𝑖 𝑡 𝑒 𝑟(𝑥)𝑙 𝑒 𝑣 𝑒 𝑙(𝑥)(𝑟 𝑛 𝑘(𝑥)))A l e v e l(x)i t e r(x)+1(r n k(x))=A l e v e l(x)(A l e v e l(x)i t e r(x)(r n k(x)))．

注意，我们可能会用 𝑘(𝑥)k(x) 代表 𝑙 𝑒 𝑣 𝑒 𝑙(𝑥)l e v e l(x)，𝑖(𝑥)i(x) 代表 𝑖 𝑡 𝑒 𝑟(𝑥)i t e r(x) 以避免式子过于冗长．这里，就是 𝑟 𝑛 𝑘(𝑟 𝑜 𝑜 𝑡 𝑥) ≥𝐴 𝑘(𝑥)(𝐴 𝑖(𝑥)𝑘(𝑥)(𝑥))r n k(r o o t x)≥A k(x)(A k(x)i(x)(x))．

当你看到这的时候，可能会有一种「这啥玩意」的感觉．这意味着你可能需要多看几遍，或者跳过一些内容以后再看．

这里，我们需要一个外接的 𝐴 𝑘(𝑥)A k(x)，意味着我们可能需要再找一个点 𝑦 y．令 𝑦 y 是搜索路径上在 𝑥 x 之后的满足 𝑘(𝑦) =𝑘(𝑥)k(y)=k(x) 的点，这里「搜索路径之后」相当于「是 𝑥 x 的祖先」．显然，不是每一个 𝑥 x 都有这样一个 𝑦 y．很容易证明，没有这样的 𝑦 y 的 𝑥 x 不超过 𝛼(𝑛) +2 α(n)+2 个．因为只有每个 𝑘 k 的最后一个 𝑥 x 和 𝑎 a 以及 𝑟 𝑜 𝑜 𝑡 𝑎 r o o t a 没有这样的 𝑦 y．

我们再强调一遍 𝑓 𝑎(𝑥)f a(x) 指的是路径压缩 之前 𝑥 x 的父节点，路径压缩 之后 𝑥 x 的父节点一律用 𝑟 𝑜 𝑜 𝑡 𝑥 r o o t x 表示．对于每个存在 𝑦 y 的 𝑥 x，总是有 𝑟 𝑛 𝑘(𝑦) ≥𝑟 𝑛 𝑘(𝑓 𝑎(𝑥))r n k(y)≥r n k(f a(x))．同时，我们有 𝑟 𝑛 𝑘(𝑓 𝑎(𝑥)) ≥𝐴 𝑖(𝑥)𝑘(𝑥)(𝑟 𝑛 𝑘(𝑥))r n k(f a(x))≥A k(x)i(x)(r n k(x))．由于 𝑘(𝑥) =𝑘(𝑦)k(x)=k(y)，我们用 𝑘 k 来统称，即，𝑟 𝑛 𝑘(𝑓 𝑎(𝑥)) ≥𝐴 𝑖(𝑥)𝑘(𝑟 𝑛 𝑘(𝑥))r n k(f a(x))≥A k i(x)(r n k(x))．我们需要造一个 𝐴 𝑘 A k 出来，所以我们可以不关注 𝑖 𝑡 𝑒 𝑟(𝑦)i t e r(y) 的值，直接使用弱化版的 𝑟 𝑛 𝑘(𝑓 𝑎(𝑦)) ≥𝐴 𝑘(𝑟 𝑛 𝑘(𝑦))r n k(f a(y))≥A k(r n k(y))．

如果我们将不等式组合起来，神奇的事情就发生了．我们发现，𝑟 𝑛 𝑘(𝑓 𝑎(𝑦)) ≥𝐴 𝑖(𝑥)+1 𝑘(𝑟 𝑛 𝑘(𝑥))r n k(f a(y))≥A k i(x)+1(r n k(x))．也就是说，为了从 𝑟 𝑛 𝑘(𝑥)r n k(x) 迭代到 𝑟 𝑛 𝑘(𝑓 𝑎(𝑦))r n k(f a(y))，至少可以迭代 𝐴 𝑘 A k 不少于 𝑖(𝑥) +1 i(x)+1 次而不超过 𝑟 𝑛 𝑘(𝑓 𝑎(𝑦))r n k(f a(y))．

显然，有 𝑟 𝑛 𝑘(𝑟 𝑜 𝑜 𝑡 𝑦) ≥𝑟 𝑛 𝑘(𝑓 𝑎(𝑦))r n k(r o o t y)≥r n k(f a(y))，且 𝑟 𝑛 𝑘(𝑥)r n k(x) 在路径压缩时不变．因此，我们可以得到 𝑟 𝑛 𝑘(𝑟 𝑜 𝑜 𝑡 𝑥) ≥𝐴 𝑖(𝑥)+1 𝑘(𝑟 𝑛 𝑘(𝑥))r n k(r o o t x)≥A k i(x)+1(r n k(x))，也就是说 𝑖 𝑡 𝑒 𝑟(𝑥)i t e r(x) 的值至少增加 1，如果 𝑟 𝑛 𝑘(𝑥)r n k(x) 没有增加，一定是 𝑙 𝑒 𝑣 𝑒 𝑙(𝑥)l e v e l(x) 增加了．

所以，Φ(𝑥)Φ(x) 至少减少了 1．由于这样的 𝑥 x 节点至少有 𝑠 −𝛼(𝑛) −2 s−α(n)−2 个，所以最后 Φ(𝑆)Φ(S) 至少减少了 𝑠 −𝛼(𝑛) −2 s−α(n)−2，均摊后的时间复杂度即为 Θ(𝛼(𝑛) +2) =Θ(𝛼(𝑛))Θ(α(n)+2)=Θ(α(n))．

## 为何并查集会被卡

这个问题也就是问，如果我们不按秩合并，会有哪些性质被破坏，导致并查集的时间复杂度不能保证为 Θ(𝑚 𝛼(𝑛))Θ(m α(n))．

如果我们在合并的时候，𝑟 𝑛 𝑘 r n k 较大的合并到了 𝑟 𝑛 𝑘 r n k 较小的节点上面，我们就将那个 𝑟 𝑛 𝑘 r n k 较小的节点的 𝑟 𝑛 𝑘 r n k 值设为另一个节点的 𝑟 𝑛 𝑘 r n k 值加一．这样，我们就能保证 𝑟 𝑛 𝑘(𝑓 𝑎(𝑥)) ≥𝑟 𝑛 𝑘(𝑥) +1 r n k(f a(x))≥r n k(x)+1，从而不会出现类似于满地 compile error 一样的性质不符合．

显然，如果这样子的话，我们破坏的就是 𝑢 𝑛 𝑖 𝑜 𝑛(𝑥,𝑦)u n i o n(x,y) 函数「y 的势能最多增加 𝛼(𝑛)α(n)」这一句．

存在一个能使路径压缩并查集时间复杂度降至 Ω(𝑚 l o g 1+𝑚 𝑛⁡𝑛)Ω(m log 1+m n⁡n) 的结构，定义如下：

二项树（实际上和一般的二项树不太一样），其中 j 是常数，𝑇 𝑘 T k 为一个 𝑇 𝑘−1 T k−1 加上一个 𝑇 𝑘−𝑗 T k−j 作为根节点的儿子．

边界条件，𝑇 1 T 1 到 𝑇 𝑗 T j 都是一个单独的点．

令 𝑟 𝑛 𝑘(𝑇 𝑘) =𝑟 𝑘 r n k(T k)=r k，这里我们有 𝑟 𝑘 =(𝑘 −1)/𝑗 r k=(k−1)/j（证明略）．每轮操作，我们将它接到一个单节点上，然后查询底部的 𝑗 j 个节点．也就是说，我们接到单节点上的时候，单节点的势能提高了 (𝑘 −1)/𝑗 +1(k−1)/j+1．在 𝑗 =⌊𝑚 𝑛⌋j=⌊m n⌋，𝑖 =⌊l o g 𝑗+1⁡𝑛 2⌋i=⌊log j+1⁡n 2⌋，𝑘 =𝑖 𝑗 k=i j 的时候，势能增加量为：

𝛼(𝑛)×((𝑖 𝑗−1)/𝑗+1)=𝛼(𝑛)×((⌊l o g⌊𝑚 𝑛⌋+1⁡𝑛 2⌋×⌊𝑚 𝑛⌋−1)/⌊𝑚 𝑛⌋+1)α(n)×((i j−1)/j+1)=α(n)×((⌊log⌊m n⌋+1⁡n 2⌋×⌊m n⌋−1)/⌊m n⌋+1)

变换一下，去掉所有的取整符号，就可以得出，势能增加量 ≥𝛼(𝑛) ×(l o g 1+𝑚 𝑛⁡𝑛 −𝑛 𝑚)≥α(n)×(log 1+m n⁡n−n m)，m 次操作就是 Ω(𝑚 l o g 1+𝑚 𝑛⁡𝑛 −𝑛) =Ω(𝑚 l o g 1+𝑚 𝑛⁡𝑛)Ω(m log 1+m n⁡n−n)=Ω(m log 1+m n⁡n)．

## 关于启发式合并

由于按秩合并比启发式合并难写，所以很多 dalao 会选择使用启发式合并来写并查集．具体来说，则是对每个根都维护一个 𝑠 𝑖 𝑧 𝑒(𝑥)s i z e(x)，每次将 𝑠 𝑖 𝑧 𝑒 s i z e 小的合并到大的上面．

所以，启发式合并会不会被卡？

首先，可以从秩参与证明的性质来说明．如果 𝑠 𝑖 𝑧 𝑒 s i z e 可以代替 𝑟 𝑛 𝑘 r n k 的地位，则可以使用启发式合并．快速总结一下，秩参与证明的性质有以下三条：

1. 每次合并，最多有一个节点的秩上升，而且最多上升 1．
2. 总有 𝑟 𝑛 𝑘(𝑓 𝑎(𝑥)) ≥𝑟 𝑛 𝑘(𝑥) +1 r n k(f a(x))≥r n k(x)+1．
3. 节点的秩不减．

关于第二条和第三条，𝑠 𝑖 𝑧 s i z 显然满足，然而第一条不满足，如果将 𝑥 x 合并到 𝑦 y 上面，则 𝑠 𝑖 𝑧(𝑦)s i z(y) 会增大 𝑠 𝑖 𝑧(𝑥)s i z(x) 那么多．

所以，可以考虑使用 l o g 2⁡𝑠 𝑖 𝑧(𝑥)log 2⁡s i z(x) 代替 𝑟 𝑛 𝑘(𝑥)r n k(x)．

关于第一条性质，由于节点的 𝑠 𝑖 𝑧 s i z 最多翻倍，所以 l o g 2⁡𝑠 𝑖 𝑧(𝑥)log 2⁡s i z(x) 最多上升 1．关于第二三条性质，结论较为显然，这里略去证明．

所以说，如果不想写按秩合并，就写启发式合并好了，时间复杂度仍旧是 Θ(𝑚 𝛼(𝑛))Θ(m α(n))．

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：orzAtalod, Enter-tainer, H-J-Granger, StudyingFather, CCXXXI, Friendseeker, iamtwz, NachtgeistW, R-fzx, Tiphereth-A, Xeonacid, yusancky
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用