5.6 哈夫曼树与并查集

带权路径长度与哈夫曼树的构造、前缀编码与哈夫曼编码；并查集的双亲表示、按大小合并与路径压缩。

哈夫曼树

带权路径长度

在许多应用中，树中结点常常被赋予一个表示某种意义的数值，称为该结点的权。从树的根到任意结点的路径长度（经过的边数）与该结点上权值的乘积，称为该结点的带权路径长度。树中所有叶结点的带权路径长度之和称为该树的带权路径长度，记为

式中，$w_i$ 是第 $i$ 个叶结点所带的权值，$l_i$ 是该叶结点到根结点的路径长度。

在含有 $n$ 个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树。

（a、b、c、d 的权值分别为 7、5、2、4）可见，权值越大的叶结点离根越近，WPL 越小。

构造哈夫曼树

给定 $n$ 个权值分别为 $w_1, w_2, \ldots, w_n$ 的结点，构造哈夫曼树的算法描述如下：

哈夫曼编码

在数据通信中，若对每个字符用相等长度的二进制位表示，称这种编码方式为固定长度编码；若允许对不同字符用不等长的二进制位表示，则这种编码方式称为可变长度编码。可变长度编码比固定长度编码要好得多，其特点是对频率高的字符赋以短编码，而对频率较低的字符则赋以较长一些的编码，从而可以使字符的平均编码长度减短，起到压缩数据的效果。

若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。前缀编码的解码很简单：因为没有一个编码是其他编码的前缀，所以识别出第一个编码，将它翻译为原字符，再对余下的编码文件重复同样的解码操作。

由哈夫曼树得到哈夫曼编码：将每个出现的字符当作一个独立的结点，其权值为它出现的频度（或次数），构造出对应的哈夫曼树。将字符的编码解释为从根至该字符的路径上边标记的序列，其中边标记为 0 表示”转向左孩子”，标记为 1 表示”转向右孩子”。由于字符都在叶结点上，哈夫曼编码一定是前缀编码。WPL 可视为最终编码得到的二进制编码长度。

并查集

并查集是一种简单的集合表示，它支持以下 3 种操作：

1. Initial(S)：将集合 S 中的每个元素都初始化为只有一个单元素的子集合；
2. Union(S, Root1, Root2)：把集合 S 中的子集合 Root2 并入子集合 Root1。要求 Root1 和 Root2 互不相交，否则不执行合并；
3. Find(S, x)：查找集合 S 中单元素 x 所在的子集合，并返回该子集合的根结点。

通常用树的双亲表示作为并查集的存储结构，每个子集合以一棵树表示。所有表示子集合的树，构成表示全集合的森林，存放在双亲表示数组内。通常用数组元素的下标代表元素名，用根结点的下标代表子集合名，根结点的双亲域为负数（可设置为该子集合元素数量的相反数）。

1int Find(int S[], int x) {
2    int root = x;
3    while (S[root] >= 0)          // 循环找到根
4        root = S[root];
5    while (x != root) {           // 路径压缩（可选）
6        int t = S[x];
7        S[x] = root;              // x 直接挂到根下
8        x = t;
9    }
10    return root;
11}
12void Union(int S[], int Root1, int Root2) {
13    if (Root1 == Root2) return;
14    if (S[Root2] > S[Root1]) {    // Root2 结点数更少
15        S[Root1] += S[Root2];     // 累加结点总数
16        S[Root2] = Root1;         // 小树合并到大树
17    } else {
18        S[Root2] += S[Root1];
19        S[Root1] = Root2;
20    }
21}

两种优化

在动画中分别勾选、取消”小树并入大树”和”路径压缩”，对比最终森林的高度。

即时练习