算法刷题系列（六十六）：哈夫曼树——用贪心构造最优前缀码

算法刷题系列（六十六）：哈夫曼树——用贪心构造最优前缀码

旧树结构笔记保留了一张哈夫曼树示意图。本篇把图补成算法：给每个符号一个出现频次，构造一棵带权路径长度最小的二叉树，再把左边记为 0、右边记为 1，得到变长前缀码。

核心贪心选择是：每一步取当前权重最小的两棵树合并。优先队列正好支持反复取出最小项，因此哈夫曼树是堆与贪心的组合应用。

一、编码长度如何计价？

若符号 i 的频次为 w[i]，它在树中的深度为 d[i]，则总编码位数为：

weightedPathLength = sum(w[i] * d[i])

高频符号放在浅层，编码短；低频符号放得较深，编码长。前缀码要求没有一个符号的编码是另一个符号编码的前缀，二叉树叶子路径天然满足这一性质。

二、为什么合并两个最小权重？

哈夫曼树每个非根内部节点都有两个孩子。最深层的两个兄弟叶子可以交换到权重最小的两个符号，而不会增加总代价；把这两个符号合并成权重之和的新符号后，原问题缩小为更少叶子的同类问题。由此得到贪心选择与最优子结构。

实际构造步骤：

1. 将所有符号作为叶节点放入最小堆；
2. 取出权重最小的两个节点；
3. 创建权重为两者之和的父节点；
4. 将新父节点放回堆；
5. 堆中只剩一个节点时，它就是根。

三、Java 实现：构造编码表

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

public class HuffmanCoding {
    static final class Node {
        final long weight;
        final String symbol;
        final Node left;
        final Node right;

        Node(long weight, String symbol, Node left, Node right) {
            this.weight = weight;
            this.symbol = symbol;
            this.left = left;
            this.right = right;
        }

        boolean isLeaf() {
            return left == null && right == null;
        }
    }

    public static Map<String, String> buildCodes(
            Map<String, Long> frequencies) {
        if (frequencies == null || frequencies.isEmpty()) {
            throw new IllegalArgumentException("frequencies must be non-empty");
        }
        PriorityQueue<Node> queue = new PriorityQueue<>(
            (first, second) -> Long.compare(first.weight, second.weight)
        );
        for (Map.Entry<String, Long> entry : frequencies.entrySet()) {
            if (entry.getKey() == null || entry.getValue() == null
                    || entry.getValue() <= 0) {
                throw new IllegalArgumentException("symbols need positive frequencies");
            }
            queue.add(new Node(entry.getValue(), entry.getKey(), null, null));
        }

        while (queue.size() > 1) {
            Node left = queue.remove();
            Node right = queue.remove();
            queue.add(new Node(
                Math.addExact(left.weight, right.weight),
                null,
                left,
                right
            ));
        }

        Map<String, String> codes = new HashMap<>();
        buildCodes(queue.remove(), new StringBuilder(), codes);
        return codes;
    }

    private static void buildCodes(
            Node node, StringBuilder path, Map<String, String> codes) {
        if (node.isLeaf()) {
            codes.put(node.symbol, path.length() == 0 ? "0" : path.toString());
            return;
        }
        path.append('0');
        buildCodes(node.left, path, codes);
        path.setLength(path.length() - 1);
        path.append('1');
        buildCodes(node.right, path, codes);
        path.setLength(path.length() - 1);
    }
}

单一符号时树只有根，空路径无法区分编码，因此约定其编码为 "0"。若频次总和可能超过 long，Math.addExact 会显式报告溢出，而不是静默生成错误权重。

四、Python 实现

from __future__ import annotations

import heapq
from dataclasses import dataclass

@dataclass
class Node:
    weight: int
    symbol: str | None = None
    left: Node | None = None
    right: Node | None = None

def build_huffman_codes(frequencies: dict[str, int]) -> dict[str, str]:
    if not frequencies:
        raise ValueError("frequencies must be non-empty")
    heap: list[tuple[int, int, Node]] = []
    serial = 0
    for symbol, weight in frequencies.items():
        if symbol is None or weight <= 0:
            raise ValueError("symbols need positive frequencies")
        heapq.heappush(heap, (weight, serial, Node(weight, symbol)))
        serial += 1

    while len(heap) > 1:
        left_weight, _, left = heapq.heappop(heap)
        right_weight, _, right = heapq.heappop(heap)
        parent = Node(left_weight + right_weight, None, left, right)
        heapq.heappush(heap, (parent.weight, serial, parent))
        serial += 1

    root = heap[0][2]
    codes: dict[str, str] = {}

    def visit(node: Node, prefix: str) -> None:
        if node.symbol is not None:
            codes[node.symbol] = prefix or "0"
            return
        if node.left is None or node.right is None:
            raise AssertionError("internal Huffman node must have two children")
        visit(node.left, prefix + "0")
        visit(node.right, prefix + "1")

    visit(root, "")
    return codes

codes = build_huffman_codes({"a": 5, "b": 2, "c": 1, "d": 1})
assert set(codes) == {"a", "b", "c", "d"}
assert len(codes["a"]) <= len(codes["c"])
assert build_huffman_codes({"only": 7}) == {"only": "0"}

若需要从编码反解消息，应保留整棵树或编码表，并沿位串逐位走到叶子；不能只保存权重和深度。

五、复杂度与验证

有 n 个不同符号时，堆中每轮减少一个节点，共进行 n - 1 次合并；每次堆操作 O(log n)，构造时间 O(n log n)，树和编码表空间 O(n)（不计输出字符串长度）。

验证编码表时，可检查任意两个不同符号编码都不存在前缀关系。编码总长度则按 sum(freq[symbol] * len(code[symbol])) 计算。

六、常见错误

1. 每次挑选并排序全部节点：虽能得到结果，但效率不如最小堆。
2. 只保留权重，丢失子树关系：没有树形结构就无法生成码字或解码。
3. 把叶子深度直接当作码字：还需要区分每一步走左还是走右。
4. 单符号输入返回空编码：应约定非空码字，本文使用 "0"。
5. 假设并列权重会得到唯一编码：不同并列处理可能生成不同码字，但加权路径长度仍可最优。

与系列其他篇章的连接

哈夫曼算法使用第 24 篇堆维护最小权重，并用贪心选择构造树；它也把树遍历与编码应用连接起来。

小结

哈夫曼树不断合并当前最小的两棵树，构造最优前缀码。正确实现需要保留节点结构、使用最小堆，并显式处理单符号、并列权重和权重溢出。