算法札记：哈夫曼树介绍及其在贪心中的应用
做《合并果子》有感
哈夫曼树介绍及其在贪心中的应用
1. 哈夫曼树定义
哈夫曼树（Huffman Tree），又称最优二叉树，是一种带权路径长度最小的二叉树。给定 nn 个叶子节点，每个叶子节点有一个权值 wiwi，则树的带权路径长度（WPL）定义为所有叶子节点的权值与其路径长度（从根到该叶子的边数）的乘积之和：
WPL=∑i=1nwi×liWPL=i=1∑nwi×li
其中 lili 是叶子节点 ii 的路径长度。哈夫曼树的目标是使 WPL 最小。
2. 贪心思想与构造算法
哈夫曼树的构造采用贪心策略：每次从森林中选取两个权值最小的树（根节点权值最小）合并成一棵新树，新树的根节点权值为两者之和。重复此过程直到只剩一棵树12。其核心在于“局部最优选择”能够导出全局最优解，这正是贪心算法的典型特征。
构造步骤（森林初始有 nn 棵单节点树）：
构造森林全是根：将 nn 个权值作为根节点，构成 nn 棵二叉树的森林。
选用两小造新树：在森林中选出两棵根权值最小的树，作为左右子树构造新二叉树，新根权值为两者之和。
删除两小添新人：从森林中移除这两棵树，并将新树加入森林。
重复 2、3 剩单根：重复步骤 2 和 3，直到森林中只剩一棵树，即为哈夫曼树3。
示例：给定权值 {5,6,7,8}{5,6,7,8}，构造过程如下：
第一次：取 55 和 66，合并为 1111，森林变为 {7,8,11}{7,8,11}。
第二次：取 77 和 88，合并为 1515，森林变为 {11,15}{11,15}。
第三次：取 1111 和 1515，合并为 2626，得到根节点 2626 的树。
最终 WPL 为 5×3+6×3+7×2+8×2=575×3+6×3+7×2+8×2=57，此值在任意二叉树中最小2。
3. 哈夫曼树的性质
包含 nn 个叶子节点的哈夫曼树共有 2n−12n−1 个节点。
所有分支节点的度均为 2（即不存在度为 1 的节点）。
节点权值越小的叶子距离根越远，权值越大的叶子距离根越近，从而保证 WPL 最小2。
4. 贪心策略的合理性
哈夫曼算法采用贪心选择性质：每次合并两个权值最小的节点，能保证最终树的总权值最小。证明思路：若存在全局最优解，则其中必然包含权值最小的两个节点作为兄弟节点（否则可调整得到更优解）。这种最优子结构和贪心选择性质使得问题可通过局部最优得到全局最优。
5. 应用：哈夫曼编码
最经典的应用是数据压缩（哈夫曼编码）。将字符出现的频率作为权值，构造哈夫曼树，左分支代表0，右分支代表1，则每个字符的编码为从根到该叶子的路径上的 0/1 序列。由于高频字符路径短、编码短，低频字符路径长、编码长，从而整体编码长度最短（即最优前缀编码），实现无损压缩。
例如，字符串“AABBC”中字符频率：A(2), B(2), C(1)。构造哈夫曼树可得编码：A:0, B:11, C:10（或类似，取决于合并顺序），压缩后总比特数小于定长编码。