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 TreeWPL。设 $w_i$ 为二叉树第 $i$ 个叶结点的权值$l_i$ 为从根结点到第 $i$ 个叶结点的路径长度则 WPL 计算公式如下$$ WPL\sum_{i1}^nw_il_i $$以 huffman-tree-1.svg 展示的二叉树为例四个叶结点权值分别为 $2,3,4,7$均处于第 2 层路径长度 $l_i2$其 WPL 计算过程与结果如下$$ WPL2\times 23\times 24\times 27\times 24681432 $$WPL 刻画了一棵带权二叉树整体代价的高低权值大的结点如果离根越近、路径越短树的 WPL 就越小。它是衡量编码方案与合并方案优劣的定量标尺。霍夫曼树的结构性质对于给定一组具有确定权值的叶结点可以构造出不同的二叉树其中WPL 最小的二叉树称为霍夫曼树Huffman Tree。霍夫曼树具有如下两个重要的结构特征权值分布特征叶结点权值越小离根越远路径越长叶结点权值越大离根越近路径越短。这正是权重高者优先贪心思想的直接体现。度数特征霍夫曼树中仅有叶结点的度为 $0$其余内部结点的度均为 $2$即不存在度为 $1$ 的单分支结点。由度数特征可以推断详见下文仓库中 docs/ds/seg.md 的类比证明若霍夫曼树有 $n$ 个叶结点则内部结点数为 $n-1$总结点数为 $2n-1$。这一性质在分析二叉树存储空间时非常实用。霍夫曼算法四步贪心构造流程霍夫曼算法用于构造一棵霍夫曼树其本质是一个自底向上的贪心合并过程算法步骤如下初始化由给定的 $n$ 个权值构造 $n$ 棵只有一个根节点的二叉树得到一个二叉树集合 $F$。选取与合并从二叉树集合 $F$ 中选取根节点权值最小的两棵二叉树分别作为左右子树构造一棵新的二叉树这棵新二叉树的根节点的权值为其左、右子树根结点的权值和。删除与加入从 $F$ 中删除作为左、右子树的两棵二叉树并将新建立的二叉树加入到 $F$ 中。重复重复第 2、3 步当集合中只剩下一棵二叉树时这棵二叉树就是霍夫曼树。以 huffman-tree-2.svg 为例初始权值集合为 ${2,4,5,3}$算法执行过程为选出最小两个权值 $2$ 与 $3$合并得到根权值为 $5$ 的新树集合变为 ${4,5,5}$选出 $4$ 与 $5$合并得到根权值为 $9$ 的新树集合变为 ${5,9}$选出 $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$我们从 $k1$ 个字母中选出两个权值最小的字母将它们合并为一棵子树子树的根作为虚拟字母虚拟结点。根据引理可知这一操作不会破坏前缀编码树的最优性。此时虚拟字母与剩下的 $k$ 个字母一同构成 $k 1$ 个字母根据归纳假设当字母数为 $k$ 时Huffman 算法能够得到最优前缀编码树。 因此通过数学归纳法Huffman 算法对于任意字母数 $n$ 都能够得到最优前缀编码树得证。上述证明的核心思路是引理保证每次合并权值最小的两棵子树这一贪心选择不会让最优解变差贪心选择的局部最优性定理则借助归纳法将局部最优选择推广到全局最优。霍夫曼编码从等长编码到最短前缀编码在进行程序设计时通常给每一个字符标记一个单独的代码来表示一组字符即编码。等长编码与不等长编码在进行二进制编码时假设所有的代码都等长那么表示 $n$ 个不同的字符需要 $\left \lceil \log_2 n \right \rceil$ 位称为等长编码。如果每个字符的使用频率相等那么等长编码无疑是空间效率最高的编码方法而如果字符出现的频率不同则可以让频率高的字符采用尽可能短的编码频率低的字符采用尽可能长的编码来构造出一种不等长编码从而获得更好的空间效率。前缀编码在设计不等长编码时要考虑解码的唯一性如果一组编码中任一编码都不是其他任何一个编码的前缀那么称这组编码为前缀编码其保证了编码被解码时的唯一性——任何一段编码流都可以被无歧义地切分还原为原始字符序列。霍夫曼编码的构造步骤霍夫曼树可用于构造最短的前缀编码即霍夫曼编码Huffman Code其构造步骤如下设需要编码的字符集为$d_1,d_2,\dots,d_n$他们在字符串中出现的频率为$w_1,w_2,\dots,w_n$。以 $d_1,d_2,\dots,d_n$ 作为叶结点$w_1,w_2,\dots,w_n$ 作为叶结点的权值构造一棵霍夫曼树。规定霍夫曼编码树的左分支代表 $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_queueint, vectorint, greaterint 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_queueint, vectorint, greaterint声明一个小根堆每次弹出两个最小元素合并并累加代价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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
OI-wiki 霍夫曼树（Huffman Tree）详解：WPL、贪心构造算法与霍夫曼编码实现
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 TreeWPL。设 $w_i$ 为二叉树第 $i$ 个叶结点的权值$l_i$ 为从根结点到第 $i$ 个叶结点的路径长度则 WPL 计算公式如下$$ WPL\sum_{i1}^nw_il_i $$以 huffman-tree-1.svg 展示的二叉树为例四个叶结点权值分别为 $2,3,4,7$均处于第 2 层路径长度 $l_i2$其 WPL 计算过程与结果如下$$ WPL2\times 23\times 24\times 27\times 24681432 $$WPL 刻画了一棵带权二叉树整体代价的高低权值大的结点如果离根越近、路径越短树的 WPL 就越小。它是衡量编码方案与合并方案优劣的定量标尺。霍夫曼树的结构性质对于给定一组具有确定权值的叶结点可以构造出不同的二叉树其中WPL 最小的二叉树称为霍夫曼树Huffman Tree。霍夫曼树具有如下两个重要的结构特征权值分布特征叶结点权值越小离根越远路径越长叶结点权值越大离根越近路径越短。这正是权重高者优先贪心思想的直接体现。度数特征霍夫曼树中仅有叶结点的度为 $0$其余内部结点的度均为 $2$即不存在度为 $1$ 的单分支结点。由度数特征可以推断详见下文仓库中 docs/ds/seg.md 的类比证明若霍夫曼树有 $n$ 个叶结点则内部结点数为 $n-1$总结点数为 $2n-1$。这一性质在分析二叉树存储空间时非常实用。霍夫曼算法四步贪心构造流程霍夫曼算法用于构造一棵霍夫曼树其本质是一个自底向上的贪心合并过程算法步骤如下初始化由给定的 $n$ 个权值构造 $n$ 棵只有一个根节点的二叉树得到一个二叉树集合 $F$。选取与合并从二叉树集合 $F$ 中选取根节点权值最小的两棵二叉树分别作为左右子树构造一棵新的二叉树这棵新二叉树的根节点的权值为其左、右子树根结点的权值和。删除与加入从 $F$ 中删除作为左、右子树的两棵二叉树并将新建立的二叉树加入到 $F$ 中。重复重复第 2、3 步当集合中只剩下一棵二叉树时这棵二叉树就是霍夫曼树。以 huffman-tree-2.svg 为例初始权值集合为 ${2,4,5,3}$算法执行过程为选出最小两个权值 $2$ 与 $3$合并得到根权值为 $5$ 的新树集合变为 ${4,5,5}$选出 $4$ 与 $5$合并得到根权值为 $9$ 的新树集合变为 ${5,9}$选出 $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$我们从 $k1$ 个字母中选出两个权值最小的字母将它们合并为一棵子树子树的根作为虚拟字母虚拟结点。根据引理可知这一操作不会破坏前缀编码树的最优性。此时虚拟字母与剩下的 $k$ 个字母一同构成 $k 1$ 个字母根据归纳假设当字母数为 $k$ 时Huffman 算法能够得到最优前缀编码树。 因此通过数学归纳法Huffman 算法对于任意字母数 $n$ 都能够得到最优前缀编码树得证。上述证明的核心思路是引理保证每次合并权值最小的两棵子树这一贪心选择不会让最优解变差贪心选择的局部最优性定理则借助归纳法将局部最优选择推广到全局最优。霍夫曼编码从等长编码到最短前缀编码在进行程序设计时通常给每一个字符标记一个单独的代码来表示一组字符即编码。等长编码与不等长编码在进行二进制编码时假设所有的代码都等长那么表示 $n$ 个不同的字符需要 $\left \lceil \log_2 n \right \rceil$ 位称为等长编码。如果每个字符的使用频率相等那么等长编码无疑是空间效率最高的编码方法而如果字符出现的频率不同则可以让频率高的字符采用尽可能短的编码频率低的字符采用尽可能长的编码来构造出一种不等长编码从而获得更好的空间效率。前缀编码在设计不等长编码时要考虑解码的唯一性如果一组编码中任一编码都不是其他任何一个编码的前缀那么称这组编码为前缀编码其保证了编码被解码时的唯一性——任何一段编码流都可以被无歧义地切分还原为原始字符序列。霍夫曼编码的构造步骤霍夫曼树可用于构造最短的前缀编码即霍夫曼编码Huffman Code其构造步骤如下设需要编码的字符集为$d_1,d_2,\dots,d_n$他们在字符串中出现的频率为$w_1,w_2,\dots,w_n$。以 $d_1,d_2,\dots,d_n$ 作为叶结点$w_1,w_2,\dots,w_n$ 作为叶结点的权值构造一棵霍夫曼树。规定霍夫曼编码树的左分支代表 $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_queueint, vectorint, greaterint 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_queueint, vectorint, greaterint声明一个小根堆每次弹出两个最小元素合并并累加代价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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
