3.2 Huffman 编码

这一篇讲贪心算法的经典应用——Huffman 编码。它是数据压缩的基石，你用的 ZIP、gzip、JPEG、MP3 底下都有它的影子。它还巧妙地把第一卷的堆（1.4，优先队列）用上了，是"贪心 + 优先队列"的标准组合。

1.问题：给字符编码，让总长度最短

假设你要用 0/1 串编码一篇文章里的字符。最朴素的是等长编码（如 ASCII 每个字符 8 位），但这没利用"有些字符出现得多、有些少"的特点——高频字符该用短码、低频字符用长码，总长度才省。

形式化：给 $n$ 个字符，每个字符 $c$ 出现频率 $f_c$ ，给每个字符分配一个 0/1 串（码字），使加权总长度 $\sum_c f_c \cdot (\text{码长}_c)$ 最小。

有个硬约束叫前缀码（prefix-free）：任何字符的码字不能是另一个字符码字的前缀。为什么必须？因为解码时，若 A 的码 "0" 是 B 的码 "01" 的前缀，遇到 "01" 就分不清是 "A,1" 还是 "B"。前缀码保证解码无歧义。前缀码对应一棵二叉树（字符在叶子，0/1 走左右），这正是 Huffman 编码的表示。

2.贪心准则：频率低的放深处

Huffman 的洞见：频率越低的字符，应该离树根越远（码越长）；频率越高的，离根越近（码越短）。 直觉很自然——少见的字给它长码无所谓，常见的字必须短。

构造方法是个自底向上的贪心：每次挑频率最低的两个节点，合并成一个新节点（新节点频率 = 两者之和）。重复直到只剩一个根。

HUFFMAN(字符频率表)
    把所有字符建成最小堆（按频率）
    while 堆里 > 1 个节点:
        x = EXTRACT-MIN   // 频率最低
        y = EXTRACT-MIN   // 次低
        z = 新节点，左右孩子 = x, y
        z.freq = x.freq + y.freq
        INSERT(z)         // 合并节点放回堆
    return 堆里剩下的（根）

最后这棵 Huffman 树，从根到每个叶子的路径就是该字符的码字（左 0 右 1）。

每轮做两次 EXTRACT-MIN（ $O(\log n)$ ）和一次 INSERT（ $O(\log n)$ ），共 $n-1$ 轮合并，所以 $O(n\log n)$ 。这里堆（优先队列）是关键——没有它，每轮找最小要 $O(n)$ 扫描，整体退化成 $O(n^2)$ 。这正是第一卷 1.4 学堆的回报：动态维护最小值、 $O(\log n)$ 取出，让贪心的"每次取最小"变得高效。

4.为什么对：贪心选择性质 + 交换论证

Huffman 的贪心对不对？同样靠证明。核心是两条：

贪心选择性质：频率最低的两个字符，一定存在某个最优编码，让它们处于最深处（兄弟叶子）。直觉：它们最不常用，放最深处（码最长）对总长影响最小，把短码留给高频字符。

最优子结构：合并两个最低频节点后，得到一个规模 $n-1$ 的子问题（用合并节点代替那两个字符）。原问题的最优解 = 子问题最优解 + 把合并节点拆回两个孩子。

证明手法是交换论证：任取一个最优树，若它没把两个最低频字符放成最深兄弟，就调整（交换）使它们到最深处——调整后总长不增。于是存在最优解让最低频两者在最深，贪心的第一步是安全的；递归下去，整个贪心正确。第四卷 4.5 会严格化。

5.Huffman 的现实意义

Huffman 编码是熵编码的代表——它逼近信息论里的熵下界（香农定理）。给定字符频率，Huffman 是最优的前缀码（在"每字符独立编码"这个框架下无法更好）。实际压缩工具（gzip、zlib）的流程通常是：先 LZ77 压缩（第十卷 10.1），再对结果做 Huffman 编码——这两步组合是 DEFLATE 算法，几乎是所有通用压缩的底层。

它体现了贪心的一个普遍模式："每次合并最小的两个"这个准则，出现在很多问题里（最优合并、最小生成树的 Kruskal 也有类似味道）。识别出这个模式，你就能把 Huffman 的思路迁移。

6.练习

Q1. 字符频率 {a:5, b:9, c:12, d:13, e:16, f:45}，手动构造 Huffman 树并写出各字符码字。

取最小的两个 5、9 合并成 14；再取 12、13 合并 25；取 14、16 合并 30；取 25、30 合并 55；取 45、55 合并 100（根）。一种可能的码字：f=0、c=100、d=101、a=1100、b=1101、e=111（具体 0/1 分配取决于左右约定，但结构由频率决定）。加权总长 = 45·1 + 12·3 + 13·3 + 5·4 + 9·4 + 16·3 = 224。

Q2. 为什么 Huffman 编码必须用前缀码？不用前缀码会怎样？

不用前缀码（某码是另一码前缀），解码会有歧义：遇到一串 0/1 无法唯一切分。前缀码保证任何码字都不是另一码字前缀，于是从左到右读，遇到完整码字就能立即解码，无需回溯。前缀码恰好对应一棵二叉树（字符在叶子），这是 Huffman 树的表示基础。

Q3.（思考题） Huffman 为什么用最小堆（优先队列）？换成每次线性扫描最小值，复杂度会怎样？

用堆，每次 EXTRACT-MIN 和 INSERT 都是 $O(\log n)$ ， $n-1$ 轮合并共 $O(n\log n)$ 。若每次线性扫描找最小，每轮 $O(n)$ ，整体退化 $O(n^2)$ 。堆的价值在于"动态维护极值、 $O(\log n)$ 取出"，让贪心"每次取最小"高效——这正是 1.4 学堆的直接回报。

7.小结

Huffman 编码用"每次合并频率最低的两个"的贪心准则，构造出最优前缀码，是数据压缩的基石。它靠最小堆实现 $O(n\log n)$ ，正确性由贪心选择性质 + 交换论证保证。下一篇我们继续贪心，进入图的世界——最小生成树的 Kruskal 算法，它还要用到第一卷的并查集。