知识总结
哈夫曼树（最优二叉树）
带权路径长度（WPL） 最小的二叉树。
$$WPL = \sum{i=1}^{n} wi \times l_i$$
其中 $wi$ 是叶节点权值，$li$ 是叶节点到根的路径长度。
构建哈夫曼树
- 将所有节点放入优先队列（最小堆）
- 每次取出权值最小的两个节点
- 创建一个新节点，权值 = 两个子节点权值之和
- 将新节点放回优先队列
- 重复2-4直到队列中只剩一个节点
哈夫曼编码
基于哈夫曼树的前缀编码：
- 左分支编码为 0，右分支编码为 1
- 频率高的字符编码短，频率低的编码长
- 任何一个字符的编码都不是另一个字符编码的前缀
示例
字符频率：A=5, B=9, C=12, D=13, E=16, F=45
构建过程：
- 合并 A(5) + B(9) = 14
- 合并 C(12) + D(13) = 25
- 合并 14 + E(16) = 30
- 合并 25 + 30 = 55
- 合并 F(45) + 55 = 100
初赛常考
- 给定频率，计算最小WPL
- 构建哈夫曼树并写出编码
- 验证是否为前缀编码
