7.4 Huffman 编码
这一节回答什么问题？
如何设计最优的前缀编码？
问题情境
你想压缩文本。不同字符出现频率不同。高频字符用短编码，低频字符用长编码。
约束：编码必须是前缀码——任何编码不能是其他编码的前缀。
Huffman 算法
- 把每个字符看作一个节点，频率作为权重
- 每次选两个最小权重的节点，合并成一个新节点（权重 = 两节点之和）
- 重复直到只剩一个节点（根）
正确性证明
两个引理：
- 最低频率字符是某最优树中深度最大的兄弟
- 合并后归结为更小的子问题（最优子结构）
本节小结
这一节解决了什么问题？
如何设计最优前缀编码？
核心方法是什么？
Huffman 算法：每次合并最小频率节点。
它为什么正确？
交换论证 + 最优子结构。
它的代价是什么？
O(n log n)（使用堆维护频率）。