加权合并启发式

概述

加权合并启发式（Weighted-Union Heuristic）是不相交集合数据结构链表表示中的优化策略。在执行 UNION 操作时，总是将较短的链表合并到较长的链表上，从而最小化指针更新的总代价。

定义

加权合并启发式

在链表表示的并查集中，每个集合用一个带头节点的单链表表示，头节点即为集合代表。每个元素维护一个指向集合代表的指针 set。

加权合并规则：执行 UNION(x, y) 时，设 $S_x$ 的大小为 $n_x$，$S_y$ 的大小为 $n_y$：

• 若 $n_x\ge n_y$：将 $S_y$ 的链表追加到 $S_x$ 的链表末尾，更新 $S_y$ 中所有元素的 set 指针指向 $S_x$ 的代表
• 若 $n_x<n_y$：反之

合并后集合大小为 $n_x+n_y$。

链表表示的数据结构

集合 S_i 的链表表示：

head ──→ [obj_1] ──→ [obj_2] ──→ [obj_3] ──→ ... ──→ [obj_ni]
           │             │             │                    │
           ↓             ↓             ↓                    ↓
         set ──→ head  set ──→ head  set ──→ head        set ──→ head

• head：链表头节点，也是集合代表
• set：每个元素指向集合代表的指针，用于 $O(1)$ 的 FIND-SET
• size：头节点维护的集合大小属性

核心性质

引理：元素指针更新次数上界

引理

在使用加权合并启发式的链表表示中，对 $n$ 个元素执行任意序列的 MAKE-SET 和 UNION 操作，每个元素的 set 指针最多被更新 $\lfloor \lg n\rfloor$ 次。

证明思路：

考虑某个元素 $x$ 的 set 指针何时会被更新。当 $x$ 所在的集合 $S_x$ 被合并到另一个更大的集合 $S_y$ 中时（即 $|S_x|<|S_y|$），$S_x$ 中的所有元素的 set 指针都需要更新。

关键观察：每次 $x$ 的 set 指针被更新，$x$ 所在集合的大小至少翻倍。

形式化地，设 $x$ 第 $k$ 次更新 set 指针后所在集合的大小为 $s_k$。由于加权合并保证 $s_{k+1}\ge 2s_k$（因为小集合合并到大集合，合并后大小至少是原来的两倍），且初始 $s_0=1$，所以：

$s_k\ge 2^k$

由于集合大小不超过 $n$，有 $2^k\le n$，即 $k\le \lfloor \lg n\rfloor$。因此每个元素最多被更新 $\lfloor \lg n\rfloor$ 次。$■$

定理19.1：总操作复杂度

定理 19.1

在使用加权合并启发式的链表表示中，对 $n$ 个元素执行 $m$ 次 MAKE-SET、UNION、FIND-SET 操作的序列，总时间为 $O(m+n\lg n)$。

证明思路（聚合分析）：

• MAKE-SET：$O(1)$ 每次，共 $O(n)$
• FIND-SET：$O(1)$ 每次（直接通过 set 指针），共 $O(m)$
• UNION：需要更新较小集合中所有元素的 set 指针
  • 由引理，每个元素最多被更新 $\lfloor \lg n\rfloor$ 次
  • $n$ 个元素的总更新次数 $\le n\lfloor \lg n\rfloor =O(n\lg n)$
  • 合并链表本身 $O(1)$

因此总时间 = $O(n)+O(m)+O(n\lg n)=O(m+n\lg n)$。$■$

操作复杂度

操作	单次代价	说明
MAKE-SET(x)	$O(1)$	创建单元素链表
FIND-SET(x)	$O(1)$	直接读取 set 指针
UNION(x, y)	$O(\min (n_x,n_y))$	更新较小集合的所有指针

局限性

加权合并启发式虽然将总复杂度从 $O(mn)$ 优化到 $O(m+n\lg n)$，但 UNION 操作的单次代价仍可能为 $O(n)$。更高效的不相交集合森林表示可以进一步将均摊代价降至 $O(\alpha (n))$。

参见

• 不相交集合数据结构 — 并查集的总览
• 不相交集合森林 — 更高效的树形表示
• 聚合分析 — 本节使用的分析方法
• 按秩合并 — 森林表示中类似的合并优化