企业官网建设流程全解析

OI-wiki 霍夫曼树（Huffman Tree）详解：WPL、贪心构造算法与霍夫曼编码实现

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

本篇技术指南以 OI-wiki 的 docs/ds/huffman-tree.md 为骨架，系统讲解霍夫曼树（Huffman Tree，又称哈夫曼树/赫夫曼树）的核心概念——树的带权路径长度（WPL）、霍夫曼树的结构性质、霍夫曼算法的四步贪心构造流程及其最优性证明，并延伸到霍夫曼编码（Huffman Code）这一最短前缀编码的构造方法。文中完整收录了仓库提供的四种 C++ 参考实现（树的构建、递归求 WPL、堆优化直接求 WPL、编码输出），并补充了仓库内 Garsia–Wachs 算法等关联知识。读完本文，你将掌握 WPL 的计算方法、霍夫曼树的构造与验证技巧，并能直接复用仓库代码解决"合并果子"等一类贪心合并最优代价问题。

树的带权路径长度（WPL）

设二叉树具有 $n$ 个带权叶结点，从根结点到各叶结点的路径长度与相应叶节点权值的乘积之和称为树的带权路径长度（Weighted Path Length of Tree，WPL）。

设 $w_i$ 为二叉树第 $i$ 个叶结点的权值，$l_i$ 为从根结点到第 $i$ 个叶结点的路径长度，则 WPL 计算公式如下：

$$ WPL=\sum_{i=1}^nw_il_i $$

以 huffman-tree-1.svg 展示的二叉树为例（四个叶结点权值分别为 $2,3,4,7$，均处于第 2 层，路径长度 $l_i=2$），其 WPL 计算过程与结果如下：

$$ WPL=2\times 2+3\times 2+4\times 2+7\times 2=4+6+8+14=32 $$

WPL 刻画了一棵带权二叉树"整体代价"的高低：权值大的结点如果离根越近、路径越短，树的 WPL 就越小。它是衡量编码方案与合并方案优劣的定量标尺。

霍夫曼树的结构性质

对于给定一组具有确定权值的叶结点，可以构造出不同的二叉树，其中，WPL 最小的二叉树称为霍夫曼树（Huffman Tree）。

霍夫曼树具有如下两个重要的结构特征：

• 权值分布特征：叶结点权值越小，离根越远（路径越长）；叶结点权值越大，离根越近（路径越短）。这正是"权重高者优先"贪心思想的直接体现。
• 度数特征：霍夫曼树中仅有叶结点的度为 $0$，其余（内部）结点的度均为 $2$，即不存在度为 $1$ 的单分支结点。

由度数特征可以推断（详见下文仓库中 docs/ds/seg.md 的类比证明）：若霍夫曼树有 $n$ 个叶结点，则内部结点数为 $n-1$，总结点数为 $2n-1$。这一性质在分析二叉树存储空间时非常实用。

霍夫曼算法：四步贪心构造流程

霍夫曼算法用于构造一棵霍夫曼树，其本质是一个自底向上的贪心合并过程，算法步骤如下：

1. 初始化：由给定的 $n$ 个权值构造 $n$ 棵只有一个根节点的二叉树，得到一个二叉树集合 $F$。
2. 选取与合并：从二叉树集合 $F$ 中选取根节点权值最小的两棵二叉树分别作为左右子树构造一棵新的二叉树，这棵新二叉树的根节点的权值为其左、右子树根结点的权值和。
3. 删除与加入：从 $F$ 中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到 $F$ 中。
4. 重复：重复第 2、3 步，当集合中只剩下一棵二叉树时，这棵二叉树就是霍夫曼树。

以 huffman-tree-2.svg 为例，初始权值集合为 ${2,4,5,3}$，算法执行过程为：

1. 选出最小两个权值 $2$ 与 $3$，合并得到根权值为 $5$ 的新树，集合变为 ${4,5,5}$；
2. 选出 $4$ 与 $5$，合并得到根权值为 $9$ 的新树，集合变为 ${5,9}$；
3. 选出 $5$ 与 $9$，合并得到根权值为 $14$ 的霍夫曼树。

值得注意的是，每轮合并会引入"合并代价 = 两棵子树权值之和"，而所有合并代价的总和恰好等于最终树的 WPL。这一等价关系使得我们可以在不显式建树的情况下直接累计代价求出 WPL，是后续堆优化代码的理论基础，也是"合并果子"等经典题目的核心考点。

最优性证明

霍夫曼算法的正确性建立在两条关键命题之上，以下完整给出仓库文档中的引理与定理及其证明。

???+ note "引理" 最优前缀编码树（Huffman 树）中的权值最小的两个叶结点总是最深的叶结点，并且将这两个结点调整为兄弟结点至少不会破坏编码树的最优性。

??? note "证明" 我们采用反证法来证明该命题。假设在一棵最优前缀编码树中，存在两个权值最小的叶结点，它们不是最深的叶结点。设这两个结点为 $a$ 和 $b$，且它们的深度小于某个最深的叶结点。对于这个最深的叶结点 $c$，我们可以将 $a$ 和 $c$ 交换位置，或将 $b$ 和 $c$ 交换位置。由于 Huffman 算法保证树的每一层按权值最小的叶结点合并，因此在交换后，树的带权路径长度（WPL）将减少。由此矛盾可得出假设不成立，因此权值最小的两个叶结点必须是最深的叶结点。

接下来，假设这两个权值最小的叶结点分别为 $a$ 和 $b$，它们的深度相同。如果在一棵最优前缀编码树中这两个结点不是兄弟结点，假设存在其他结点 $c$ 和 $d$ 与 $a$ 和 $b$ 分别是兄弟结点（假设 $a$ 和 $c$ 是兄弟结点，$b$ 和 $d$ 是兄弟结点）。我们可以将 $a$ 和 $b$ 合并为一个子树。 - 如果 $a$ 和 $b$ 合并后的权值之和小于 $c$ 或 $d$ 的权值，那么我们可以将合并后的子树与权值较大的结点（如 $c$ 或 $d$）合并，形成新的子树，WPL 会减少。 - 如果 $a$ 和 $b$ 的权值之和不小于 $c$ 和 $d$ 的权值，我们可以直接将 $a$ 和 $b$ 调整为兄弟结点，$c$ 和 $d$ 作为另一个兄弟结点，WPL 不会增加。 因此，经过这样的调整，最优性不会被破坏，得证。

???+ note "定理" Huffman 算法得到的前缀编码树是最优前缀编码树。

??? note "证明" 我们使用数学归纳法来证明该定理。

- **基本情况**：当字母数 $n = 2$ 时，显然，直接将两个字母合并成一棵树即为最优编码树。 - **归纳假设**：假设对于字母数 $n = k$（$k \geq 2$）时，Huffman 算法能够得到最优前缀编码树。 - **归纳步骤**：对于字母数 $n = k + 1$，我们从 $k+1$ 个字母中选出两个权值最小的字母，将它们合并为一棵子树，子树的根作为虚拟字母（虚拟结点）。根据引理可知，这一操作不会破坏前缀编码树的最优性。此时，虚拟字母与剩下的 $k$ 个字母一同构成 $k + 1$ 个字母，根据归纳假设，当字母数为 $k$ 时，Huffman 算法能够得到最优前缀编码树。 因此，通过数学归纳法，Huffman 算法对于任意字母数 $n$ 都能够得到最优前缀编码树，得证。

上述证明的核心思路是：引理保证"每次合并权值最小的两棵子树"这一贪心选择不会让最优解变差（贪心选择的局部最优性），定理则借助归纳法将局部最优选择推广到全局最优。

霍夫曼编码：从等长编码到最短前缀编码

在进行程序设计时，通常给每一个字符标记一个单独的代码来表示一组字符，即编码。

等长编码与不等长编码

在进行二进制编码时，假设所有的代码都等长，那么表示 $n$ 个不同的字符需要 $\left \lceil \log_2 n \right \rceil$ 位，称为等长编码。

如果每个字符的使用频率相等，那么等长编码无疑是空间效率最高的编码方法；而如果字符出现的频率不同，则可以让频率高的字符采用尽可能短的编码，频率低的字符采用尽可能长的编码，来构造出一种不等长编码，从而获得更好的空间效率。

前缀编码

在设计不等长编码时，要考虑解码的唯一性：如果一组编码中任一编码都不是其他任何一个编码的前缀，那么称这组编码为前缀编码，其保证了编码被解码时的唯一性——任何一段编码流都可以被无歧义地切分还原为原始字符序列。

霍夫曼编码的构造步骤

霍夫曼树可用于构造最短的前缀编码，即霍夫曼编码（Huffman Code），其构造步骤如下：

1. 设需要编码的字符集为：$d_1,d_2,\dots,d_n$，他们在字符串中出现的频率为：$w_1,w_2,\dots,w_n$。
2. 以 $d_1,d_2,\dots,d_n$ 作为叶结点，$w_1,w_2,\dots,w_n$ 作为叶结点的权值，构造一棵霍夫曼树。
3. 规定霍夫曼编码树的左分支代表 $0$，右分支代表 $1$，则从根结点到每个叶结点所经过的路径组成的 $0$、$1$ 序列即为该叶结点对应字符的编码。

huffman-tree-3.svg 给出了一个完整的霍夫曼编码实例：字符集 ${A,B,C,D,E}$ 的频率分别为 ${35,25,15,15,10}$，按其构造霍夫曼树后，左分支记 $0$、右分支记 $1$，得到编码表为 A→11、B→00、C→01、D→101、E→100。可以验证：任一编码都不是其他编码的前缀（如10是101与100的前缀，但10本身未被分配给任何字符），因此解码过程具有唯一性；同时频率最高的 A 获得最短的 2 位编码，频率最低的 E 获得最长的 3 位编码，符合"高频短码、低频长码"的压缩原则。

示例代码：四种 C++ 参考实现

以下代码全部来自仓库文档 docs/ds/huffman-tree.md，覆盖了霍夫曼树从构建、求 WPL 到输出编码的完整生命周期。

霍夫曼树的构建

用指针结构体表示树结点，通过反复扫描森林数组选取两个最小权值根来合并建树，时间复杂度为 $O(n^2)$：

struct HNode { int weight; HNode *lchild, *rchild; }; using Htree = HNode *; Htree createHuffmanTree(int arr[], int n) { Htree forest[N]; Htree root = NULL; for (int i = 0; i < n; i++) { // 将所有点存入森林 Htree temp; temp = (Htree)malloc(sizeof(HNode)); temp->weight = arr[i]; temp->lchild = temp->rchild = NULL; forest[i] = temp; } for (int i = 1; i < n; i++) { // n-1 次循环建霍夫曼树 int minn = -1, minnSub; // minn 为最小值树根下标，minnsub 为次小值树根下标 for (int j = 0; j < n; j++) { if (forest[j] != NULL && minn == -1) { minn = j; continue; } if (forest[j] != NULL) { minnSub = j; break; } } for (int j = minnSub; j < n; j++) { // 根据 minn 与 minnSub 赋值 if (forest[j] != NULL) { if (forest[j]->weight < forest[minn]->weight) { minnSub = minn; minn = j; } else if (forest[j]->weight < forest[minnSub]->weight) { minnSub = j; } } } // 建新树 root = (Htree)malloc(sizeof(HNode)); root->weight = forest[minn]->weight + forest[minnSub]->weight; root->lchild = forest[minn]; root->rchild = forest[minnSub]; forest[minn] = root; // 指向新树的指针赋给 minn 位置 forest[minnSub] = NULL; // minnSub 位置为空 } return root; }

实现要点：forest数组以NULL标记已合并删除的树；每轮建树后仅保留新根在minn位置，保证循环 $n-1$ 次后森林中只剩一棵树。

对已建成的树递归求 WPL

树已建好时，可通过深度优先遍历累计"叶结点权值 × 路径长度"：

struct HNode { int weight; HNode *lchild, *rchild; }; using Htree = HNode *; int getWPL(Htree root, int len) { // 递归实现，对于已经建好的霍夫曼树，求 WPL if (root == NULL) return 0; else { if (root->lchild == NULL && root->rchild == NULL) // 叶节点 return root->weight * len; else { int left = getWPL(root->lchild, len + 1); int right = getWPL(root->rchild, len + 1); return left + right; } } }

未建树直接求 WPL（小根堆优化）

利用"所有合并代价之和 = WPL"的性质，配合小根堆（优先队列）可将单次选取最小两棵的时间降到 $O(\log n)$，总复杂度 $O(n\log n)$：

int getWPL(int arr[], int n) { // 对于未建好的霍夫曼树，直接求其 WPL priority_queue<int, vector<int>, greater<int>> huffman; // 小根堆 for (int i = 0; i < n; i++) huffman.push(arr[i]); int res = 0; for (int i = 0; i < n - 1; i++) { int x = huffman.top(); huffman.pop(); int y = huffman.top(); huffman.pop(); int temp = x + y; res += temp; huffman.push(temp); } return res; }

这是竞赛中最常用的写法：priority_queue<int, vector<int>, greater<int>>声明一个小根堆，每次弹出两个最小元素合并并累加代价res，恰好 $n-1$ 轮后res即为 WPL。经典的"合并果子"（NOIP2004 提高组）问题即为该模型的直接应用。

对给定序列输出霍夫曼编码

在已建好的霍夫曼树上做一次先序遍历，用数组arr记录从根到当前结点的路径（左子为 0、右子为 1），到达叶结点时输出：

struct HNode { int weight; HNode *lchild, *rchild; }; using Htree = HNode *; void huffmanCoding(Htree root, int len, int arr[]) { // 计算霍夫曼编码 if (root != NULL) { if (root->lchild == NULL && root->rchild == NULL) { printf("结点为 %d 的字符的编码为: ", root->weight); for (int i = 0; i < len; i++) printf("%d", arr[i]); printf("\n"); } else { arr[len] = 0; huffmanCoding(root->lchild, len + 1, arr); arr[len] = 1; huffmanCoding(root->rchild, len + 1, arr); } } }

len记录当前深度（即编码长度），arr[0..len-1]即为叶结点对应的 $0/1$ 编码序列。

仓库关联知识：线性时间算法与节点数证明

霍夫曼树与编码的思想在 OI-wiki 的其他文档中也有延伸，可作为深入学习路径：

• Garsia–Wachs 算法（见 docs/misc/garsia-wachs.md）：该算法可以在线性时间内构建最优二叉查找树和字母霍夫曼码。与标准霍夫曼码不同，按此法构造的霍夫曼码是按字母顺序排列的——二进制码的排序顺序与值的输入顺序一致；若一个值的权重是它在编码消息中的频率，那么 Garsia–Wachs 算法的输出就是按字母顺序排列的、能使消息长度压缩到最短的霍夫曼代码。适合需要在"编码有序性"上有额外约束的场景。
• 线段树节点数的类比证明（见 docs/ds/seg.md）：当线段树使用内存池管理节点时，自底向上观察可知每两个底层节点合并为一个上层节点，因此可以类似哈夫曼树地证明：若有 $n$ 个叶子节点，这样的线段树总共有 $2n-1$ 个节点，其空间效率优于堆式存储且是可能的最优情况。这体现了霍夫曼树"两两合并、$2n-1$ 节点"的结构性质在数据结构空间分析中的通用价值。

小结

本文完整覆盖了霍夫曼树的核心知识链：WPL 定义与计算 → 霍夫曼树结构性质 → 四步贪心构造算法 → 引理与定理的最优性证明 → 霍夫曼编码的构造 → 四种可直接复用的 C++ 实现。其中"小根堆累计合并代价求 WPL"的写法是竞赛中的高频套路，建议读者结合仓库文档 docs/ds/huffman-tree.md 中的 SVG 示意图与 docs/misc/garsia-wachs.md 的线性时间扩展，进一步理解贪心合并类问题在更复杂场景下的应用。

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki