---
title: "Huffman Coding"
summary: Greedy tree-building for optimal prefix codes, the sibling property, and the same algorithm hiding in "merge stones", "minimum cost tree", and optimal alphabetic coding.
difficulty: core
tags: [greedy, heap, trees, dp]
time: n log n
prereq: [trees/diameter, structures/heap]
see: [structures/heap, structures/trie]
---

:::definition label="Prefix code"
An assignment of binary strings (codewords) to $n$ symbols such that no codeword is a prefix of another. Decoding is then instantaneous: walk the bit stream down the code tree, output at each leaf, restart. Equivalently: a full binary tree with the symbols at its leaves, cost $= \sum_i w_i \cdot \operatorname{depth}(\ell_i)$.
:::

:::theorem title="Huffman's algorithm is optimal"
Repeatedly take the two minimum-weight items, merge them into a parent whose weight is the sum, and push it back. The resulting tree minimises $\sum_i w_i \operatorname{depth}(\ell_i)$ over all prefix codes.
:::

:::proof
Two steps.
*(i) Deepest-pair siblings.* In an optimal tree, let $a,b$ be two deepest leaves; they are siblings at the same depth (otherwise move a shallower "uncle" subtree up, which strictly improves the cost — the standard sibling property). So an optimal tree exists where the two **minimum** weights $w_1 \le w_2$ are siblings at maximum depth: if $x,y$ occupy that deepest sibling pair, swapping $x \leftrightarrow$ the symbol of weight $w_1$ changes the cost by $(w_1 - w_x)(d - d_x) \le 0$, and similarly for $w_2$.
*(ii) Induction.* Merging $w_1,w_2$ into $w_1 + w_2$ turns the problem into the same problem on $n-1$ weights: $\sum_i w_i d_i$ for the original = $\sum_{i>2} w_i d_i' + (w_1 + w_2)(d' + 1)$ for the reduced instance, i.e. it differs by the constant $w_1 + w_2$. So an optimal reduced tree extends to an optimal original tree, and the greedy choice is safe. ∎
:::

```cpp huffman.cpp
priority_queue<long long, vector<long long>, greater<long long>> pq;
for (long long f : freq) pq.push(f);
long long cost = 0;
while (pq.size() > 1) {
    long long a = pq.top(); pq.pop();
    long long b = pq.top(); pq.pop();
    cost += a + b;                 // every merge pays the new node's weight
    pq.push(a + b);
}
// cost == sum of internal node weights == sum w_i * depth_i
```

:::note title="The identity that makes 'merge stones' the same problem"
$\sum_i w_i \cdot \operatorname{depth}_i = \sum_{\text{internal } x} \operatorname{wt}(x)$. Each leaf $i$ contributes $w_i$ to exactly the internal nodes on its path to the root, of which there are $\operatorname{depth}_i$. So "merge two piles at cost = their sum, minimise total cost" **is** Huffman — and the greedy proof above is the proof for both.
:::

:::props title="Four disguises of the same algorithm"
- **Minimum Cost Tree From Leaf Values** (LeetCode 1130 / CF-style): "merge adjacent" is *not* Huffman — adjacency forces the **optimal alphabetic** variant, solved by Hu–Tucker in $O(n\log n)$ or DP in $O(n^2)$ / Garsia–Wachs in $O(n\log n)$. Huffman without adjacency would ignore the order and be wrong;
- **Huffman with bounded depth** (e.g. "code lengths $\le L$"): the package-merge algorithm (van Leeuwen) $O(nL)$, or "MOPT-Merge" — do not try to patch the greedy with a heap trick;
- **$k$-ary Huffman**: merge the $k$ smallest at a time; pad with $k - 1 - ((n-2) \bmod (k-1))$ zero-weight symbols first so the last merge also takes exactly $k$ — forgetting the padding is the classic $k$-ary bug;
- **Optimal merge pattern / file merging**, **carpenter's board**, **"connect ropes with minimum cost"**: exactly the binary case, cost = total merge weight.
:::

:::example title="Emitting the code"
Keep node ids in the heap, build the tree with explicit children, then DFS assigning `0`/`1`. Real formats use a **canonical** code instead: compute the lengths $\ell_i$, sort symbols by $(\ell_i, i)$, and set
$$\text{code}_i = (\text{code}_{i-1} + \text{count}(\ell_{i-1})) \ll (\ell_i - \ell_{i-1}),$$
so transmitting the *length table* suffices to rebuild the code — the reason DEFLATE and JPEG send lengths rather than codewords, and the general lesson that a tree you can serialise in $O(n)$ bits of "shape plus counts" is worth more than the tree itself (@trees/counting's Prüfer bijection is the same economy).
:::

:::warning title="Two facts to state when asked"
1. Huffman is optimal among **prefix codes with per-symbol integer lengths**; it is *not* optimal among all codes for a source — arithmetic coding beats it by using fractional effective lengths, so "Huffman is optimal" always needs the qualifier.
2. Ties matter: with equal weights different trees give different *lengths* (same cost). If the problem asks for a lexicographically smallest code or minimal maximum length, break ties by (weight, subtree size, smallest symbol in subtree) — this is the whole difficulty of several problems.
:::

:::problems
- [[CSES 1631]] Reading Books | https://cses.fi/problemset/task/1631 | easy | the "max vs half" edge case where Huffman-style merging degenerates
- [[CSES 1073]] Towers | https://cses.fi/problemset/task/1073 | easy | the same "extract an extreme from a heap" skeleton, different greedy
- [[CF 9D]] How many trees? | https://codeforces.com/problemset/problem/9/D | hard | counting the trees Huffman builds: DP over (nodes, depth) instead of merging them
:::