# 哈夫曼树 ## 定义 给定 $n$ 个数值 $w_i$ 作为 $n$ 个叶子结点的权值，构建一棵含有这 $n$ 个叶子结点的二叉树，要求最小化二叉树的**带权路径长度**（WPL） $\sum w_il_i$，其中 $l_i$ 为叶子结点 $i$ 到树根的距离。 ## 构建 ### 思路 贪心：$w_i$ 越小的结点的 $l_i$ 应尽可能大。 每次选择权值最小的且没有父亲的两个结点，令它们权值为 $x, y$，新建一个权值为 $x + y$ 的结点，并将该结点作为之前选择的两个结点的父亲。 ### 步骤 1. 将 $n$ 个结点压入堆中，优先级最高的结点为权值最小的。 2. 执行以下步骤 $n - 1$ 次： 1. 弹出堆中的权值最小的两个结点 $u, v$，令值为 $w_u, w_v$。 2. 新建一个权值为 $w_u + w_v$ 的结点 $p$，压入堆中，并且令该结点为 $u, v$ 的父亲。 在构建哈夫曼树，可以顺便求出带权路径长度 WPL。 ## 哈夫曼编码 哈夫曼编码是一种前缀编码，指任何一个字符的编码都不是另一个字符编码的前缀。前缀边的优点在于保证了解码的唯一性。具体例子如下： ``` 字符：A B C D E 编码：100 10 11 1 0 编码：10100111 一种可能的字符串：BACD 另一种可能的字符串：DEACD 不能准确将编码翻译为字符，因为有些字符的编码是其他编码的前缀 字符：A B C D E 编码：1100 111 1101 10 0 编码：1111100110110 字符串：BACD 如果满足任意一个字符的编码均不是其他所有字符的编码的前缀，可以准确将编码翻译为字符串 ``` 给定字符串和字符串中 $n$ 种字符的出现次数，要求给字符进行一种不定长度的二进制编码，使得将字符串按照编码规则翻译为二进制串后的总长度最小（在所有的前缀编码中最小）。 将 $n$ 种字符的出现次数构建哈夫曼树，对于树上每个结点，左儿子边为 $0$，右儿子边为 $1$，从树根到叶子结点的路径的二进制串，就是该叶子对应的字符的二进制编码。通过这种方式得到的编码规则就是哈夫曼编码。 ## 习题 ### 洛谷 P1090 合并果子 贪心，每次选出数目最小的两堆进行合并即可。暴力模拟是 $O(n^2)$，可以用优先队列优化至 $O(n \log n)$。 如果把合并过程建树，那么题目所要求的的答案就是 $\sum a_id_i$，$a_i$ 为数目，$d_i$ 为 $a_i$ 在树中的深度，显然 $d_i$ 大的叶子结点 $a_i$ 尽可能小，因此每次选出数目最小的两堆进行合并。 ### 洛谷 P2168 荷马史诗 类似于哈夫曼树，用同样的贪心策略建一棵 $k$ 叉树。$w_i$ 为每个字符出现次数，$l_i$ 为每个字符的 $k$ 进制编码的长度。 如果每次都是取出 $k$ 个最小的权值，仔细发现，最终剩下的堆的大小可能在 $[2, k - 1]$ 之间。例如，$n = 4, k = 3$，最终堆剩下 $2$ 个结点。 错误策略：将堆中剩下的所有结点取出，并连向最终的树根。例如，将一个叶子结点连向树根，可以让 $\sum w_il_i$ 更小。  当 $n = k, 2k - 1, 3k - 2, 4k - 3, \dots = b * (k - 1) + 1 \ (b \ge 1)$，最终堆只会剩下 $1$ 个结点，即树根。 分类讨论求解文章的最短编码长度： - 当 $(n - 1) \bmod (k - 1) = 0$，按上述做法直接做。 - 当 $(n - 1) \bmod (k - 1) \ne 0$，一开始先加入 $k - 1 - (n - 1) \bmod (k - 1)$ 个 $0$，然后按上述做法直接做。$0$ 一定是在最深的叶子中出现，树的高度也尽可能小。 第二问实际在问需要用尽可能短的 $k$ 进制串来编码。当 $n = 7, k = 3, w = [1, 1, 1, 3, 3, 3, 3]$ 时，有两种以下的哈夫曼树使得最终文章长度都是最短的：  这提示我们在取出权值最短的结点时，还需要考虑当前结点对应的子树的高度。当权值不同时优先取权值小的结点，当权值相同时优先取子树深度小的结点。