算法札记：哈夫曼树介绍及其在贪心中的应用

做《合并果子》有感哈夫曼树介绍及其在贪心中的应用1. 哈夫曼树定义哈夫曼树Huffman Tree又称最优二叉树是一种带权路径长度最小的二叉树。给定 nn 个叶子节点每个叶子节点有一个权值 wiwi​则树的带权路径长度WPL定义为所有叶子节点的权值与其路径长度从根到该叶子的边数的乘积之和WPL∑i1nwi×liWPLi1∑n​wi​×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×36×37×28×2575×36×37×28×257此值在任意二叉树中最小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或类似取决于合并顺序压缩后总比特数小于定长编码。