JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Huffman Coding

How do you give the commonest letters the shortest codes without ever confusing where one code ends and the next begins? Huffman's greedy answer builds the optimal prefix code bottom-up by repeatedly merging the two least-frequent symbols — and an exchange argument proves no code can do better.

The problem: short codes for common symbols

Suppose you want to store a long text using bits. The lazy way gives every character the same number of bits — say 8 bits each, as ASCII does. But that wastes space: in English the letter 'e' appears constantly while 'q' is rare, yet both pay the same 8 bits. The natural idea is a variable-length code — short bit-strings for common symbols, longer ones for rare symbols — so that the total number of bits, weighted by how often each symbol occurs, comes out as small as possible. This is an optimization problem: among all legal codes, find the one minimizing the expected code length.

There is a catch that makes this harder than it looks. If 'a' is coded as 0 and 'b' as 01, then the bit-string 001 is ambiguous — it could be 'a','a','b'... wait, no, 0-0-1 is not even decodable, because nothing starts with the leftover 1, and 0-01 reads as 'a','b' while 00-1 reads as nonsense. The cure is the prefix-free property: no symbol's code may be a prefix of another symbol's code. If no codeword is a prefix of any other, then as you read bits left to right, the moment the bits you have seen match a codeword, that match is unique and unmistakable — you decode it, and start fresh.

Huffman's greedy move

Here is the greedy idea, and it is delightfully simple. Look at the two symbols with the smallest frequencies. Whatever the optimal tree turns out to be, those two rarest symbols can safely be made siblings at the very bottom — give them a parent, treat that parent as a brand-new symbol whose frequency is the sum of the two, and forget the originals. Then repeat on the smaller set. Each merge removes two symbols and adds one, so after enough merges only a single symbol remains: the root of the finished tree. This is the Huffman algorithm, and it builds the tree from the leaves upward rather than the root down.

while more than one symbol remains:
    x = extract symbol of smallest frequency
    y = extract symbol of next-smallest frequency
    z = new node with freq(z) = freq(x) + freq(y)
    make x and y the two children of z
    insert z back into the pool
the last remaining node is the root
Huffman's loop: repeatedly merge the two least-frequent items, reinsert the merged node, until one tree remains.

Trace it on frequencies a:5, b:2, c:1, d:1. The two smallest are c:1 and d:1; merge them into a node (cd):2. The pool is now a:5, b:2, (cd):2. The two smallest are b:2 and (cd):2; merge into (bcd):4. The pool is a:5, (bcd):4. Merge those into the root:9. Reading the tree, a gets the short code (depth 1) while c and d get the long codes (depth 3) — exactly the shape we wanted, with the common 'a' cheap and the rare 'c','d' paying more. The total cost is 5·1 + 2·2 + 1·3 + 1·3 = 15 bits, which you can check beats any fixed-length scheme here.

What does this cost to run? Each round needs the two smallest frequencies, which is exactly what a min-priority-queue (a binary heap) gives cheaply. With n symbols you do about n merges, each doing two extract-mins and one insert at O(log n) apiece, so the whole thing is O(n log n). (If the frequencies arrive already sorted, two queues let you do it in O(n).) The algorithm is short, fast, and — unlike many greedy methods — provably optimal, which is the part we turn to next.

Why merging the two rarest is safe: the greedy-choice property

The whole proof rests on one claim, the greedy-choice property for this problem: some optimal tree has the two least-frequent symbols, call them x and y, as sibling leaves at the deepest level. If we can show that, the greedy first move never closes off the optimum — there is always an optimal tree agreeing with what greedy just did. As you saw in the earlier guides of this rung, this is the recurring engine of every greedy proof: show that the greedy choice is compatible with optimality, then recurse.

We prove it with an exchange argument, the same tool you met two guides ago. Take any optimal tree T. Let a and b be the two symbols sitting deepest in T as siblings (a full binary tree always has two such sibling leaves at the bottom). Now x and y are the globally least-frequent symbols, so freq(x) ≤ freq(a) and freq(y) ≤ freq(b). Swap x with a, and y with b. Each swap moves a low-frequency symbol deeper and a higher-frequency symbol shallower — and since cost is frequency times depth, that exchange can only decrease the total, never increase it.

  1. Let T be any optimal tree, and let a, b be a deepest pair of sibling leaves in T. By the algorithm's choice, x and y are the two symbols of smallest frequency overall.
  2. Swap x with a. The change in cost is (freq(x) - freq(a)) × (depth(a) - depth(x)). Both factors have the right sign — x is no more frequent than a, and a sits at least as deep as x — so the product is ≤ 0: the cost does not go up.
  3. Swap y with b for the same reason; again cost does not rise. The result is a tree T' that is still optimal (its cost is ≤ T's, and T was optimal, so it equals T's) and now has x and y as deepest siblings — exactly the configuration greedy commits to.

Closing the loop: optimal substructure and induction

The greedy-choice property handles only the first merge. To prove the whole algorithm optimal we also need optimal substructure: after we fuse x and y into a single super-symbol z with freq(z) = freq(x) + freq(y), an optimal tree for the smaller problem (with z in place of x and y) extends to an optimal tree for the original simply by splitting z back into its two children. The cost bookkeeping works out exactly: replacing z's leaf by an internal node with leaves x and y adds freq(x) + freq(y) to the total, which is precisely freq(z), so optimizing the reduced problem optimizes the original.

With both pieces in hand, the correctness proof is a clean induction on the number of symbols. The base case is one symbol — a one-node tree, trivially optimal. For the inductive step, assume Huffman is optimal on every instance of n-1 symbols. Given n symbols, greedy's first merge is safe by the greedy-choice property, the rest is an (n-1)-symbol instance solved optimally by the induction hypothesis, and optimal substructure stitches the two together. So Huffman is optimal on n symbols, completing the induction.

It is worth pausing on how much these two properties carry. The greedy-choice property is what lets us commit to a move without looking ahead; optimal substructure is what lets the committed move shrink the problem to a smaller copy of itself. Every clean greedy proof — the one for interval scheduling you saw earlier, the ones for Prim's and Kruskal's spanning trees you will meet — is exactly this pair: a safe first choice plus a self-similar remainder. When both hold, greedy is not a heuristic that 'usually works'; it is exactly correct.

Honest edges: what Huffman does and does not promise

Be precise about the claim. Huffman gives the optimal prefix-free, symbol-by-symbol code for a fixed set of frequencies — that is genuinely optimal, no asterisk, within that arena. But the arena has walls. It does not promise the smallest possible compressed file in general, because real compressors exploit structure Huffman ignores: correlations between neighboring symbols, repeated substrings, and the fact that you can sometimes spend a fractional number of bits per symbol. Arithmetic coding, for instance, can beat Huffman precisely because Huffman is stuck giving each symbol a whole number of bits.

There is also a quiet honesty about the inputs. The cost Huffman minimizes — sum over symbols of frequency × depth — is an average over the symbol distribution you fed it. If you feed it frequencies from one text and then encode a different text whose symbol mix is unlike it, the code can be far from optimal for that second text, just as average-case running times only describe the distribution you assumed. The optimality is relative to the frequencies given, not a universal guarantee for whatever data shows up later.

Finally, take Huffman as a reassuring exception rather than a license. Greedy stumbles far more often than it succeeds; the very next guide builds the 0/1 knapsack, where the same 'take the locally best item' instinct that wins for fractional knapsack flatly fails, and then shows that the structures where greedy provably works (like Huffman's tree-building and the spanning-tree algorithms) are captured by the abstraction of a matroid. Huffman is the happy case where a careful exchange argument turns a simple, fast, locally-greedy loop into a theorem.