哈夫曼编码是一种无损数据压缩方法。它根据每个字符出现的频率给字符分配一个变长的二进制码：频率越高的字符，码越短。最终消息的总比特数比定长编码（如 ASCII 每个字符 8 位）更少。
为什么需要”前缀码”
如果用 a=0, b=1, c=01，那 “01” 既可以解析为 “ab” 也可以解析为 “c” —— 歧义。
前缀码：任意字符的码不是另一个字符码的前缀。哈夫曼码天然就是前缀码 —— 因为每个字符都对应叶子节点，路径上不可能再有其他字符。
贪心算法（霍夫曼，1952）
每次从森林里取出权值最小的两棵树合并，新树的权值是两者之和，放回队列。重复直到只剩一棵 —— 那就是哈夫曼树。
priority_queue<Node*> pq;
for (auto [c, f] : freq) pq.push(new Node{f, c});
while (pq.size() > 1) {
Node* a = pq.top(); pq.pop();
Node* b = pq.top(); pq.pop();
pq.push(new Node{a->w + b->w, '\0', a, b});
}导出编码：从根 DFS，向左走加 0，向右走加 1。走到叶子时累计的字符串就是该叶子字符的编码。
为什么贪心是最优的
合并最小的两棵这件事很反直觉 —— 凭什么保证全局最优？关键引理是：
在最优树中，频率最低的两个字符一定是最深的两个叶子，并且是兄弟。
证明大致是反证法 + 交换论证：如果不是兄弟，把它俩交换到一起不会让总代价变差。这条性质让贪心选择安全：当前最小的两个必然占据某棵最优树的最深一对兄弟位置。其余部分递归地变成更小的子问题。
复杂度
- 时间：O(n log n) —— n 次合并，每次堆操作 O(log n)
- 空间：O(n) —— 树有 2n - 1 个节点
在动画里看什么
- 初始：每个字符各成一棵单节点树
- 蓝色高亮：每次被弹出的两棵最小树
- 红色高亮：刚合并产生的新内部节点
- 边上的
0/1标签：左为 0，右为 1 - 完成后下方出现编码表 —— 高频字符（如
'a'）的码会明显比低频字符（如'f'）的码短
经典数字
CLRS 教科书的标准例子 {a:45, b:13, c:12, d:16, e:9, f:5} 的最优总码长是 224 bits。如果用定长 3 bit 编码（6 个字符可以塞下），总长是 100 × 3 = 300 bits —— 节省 25%。