Chapter 11 · Advanced Tree Algorithms
Huffman Coding
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.
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 = ∑i wi · depth(ℓi).
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 ∑i wi depth(ℓi) over all prefix codes.
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 w1 ≤ w2 are siblings at maximum depth: if x,y occupy that deepest sibling pair, swapping x rightarrow the symbol of weight w1 changes the cost by (w1 - wx)(d - dx) ≤ 0, and similarly for w2. (ii) Induction. Merging w1,w2 into w1 + w2 turns the problem into the same problem on n-1 weights: ∑i wi di for the original = ∑i>2 wi di' + (w1 + w2)(d' + 1) for the reduced instance, i.e. it differs by the constant w1 + w2. So an optimal reduced tree extends to an optimal original tree, and the greedy choice is safe. ∎
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∑i wi · depthi = ∑internal x wt(x). Each leaf i contributes wi to exactly the internal nodes on its path to the root, of which there are depthi. So "merge two piles at cost = their sum, minimise total cost" is Huffman — and the greedy proof above is the proof for both.
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(nlog n) or DP in O(n2) / Garsia–Wachs in O(nlog n). Huffman without adjacency would ignore the order and be wrong;
- Huffman with bounded depth (e.g. "code lengths ≤ 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) mod (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.
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 ℓi, sort symbols by (ℓi, i), and set
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 (Counting Trees: Cayley and Prüfer's Prüfer bijection is the same economy).
- 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.
- 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.