---
title: "Huffman Coding"
description: "Merge the two rarest symbols until one tree encodes them all"
source: https://vizlearn.app/algorithms/greedy/huffman-coding
access: premium (interactive player requires Lifetime; this doc is free)
---

# Huffman Coding

Huffman coding is a greedy compression algorithm that builds an optimal prefix-free binary code from symbol frequencies. It repeatedly merges the two rarest symbols into one subtree, so rare symbols sink deep into the tree and frequent symbols stay near the root. Encoding `ABRACADABRA` this way costs 23 bits; a fixed-length code needs 33.

Morse had the right instinct a century earlier: E, the most common English letter, got a single dot, while Q got a four-symbol growl. Huffman coding is that instinct made provably optimal — and made honest. Morse cheats by pausing between letters; a bitstream has no pauses, so Huffman has to build a code where no symbol's bits are the prefix of another's. The tree does that for free.

## How Huffman Coding Works

Count each symbol's frequency, then put every symbol into a min-priority queue as a one-node tree weighted by its count. Now repeat one move until a single tree remains: pop the two lightest trees, hang them under a new parent whose weight is their sum, and push the parent back in. That is the entire algorithm. The greedy rule — always merge the two rarest first — is what buries cheap, rare symbols at the bottom while expensive, frequent symbols keep floating up.

When one tree remains, read off the codes: walk from the root to each symbol's leaf, writing `0` for every left edge and `1` for every right edge. A symbol's code is its path, so its code length is exactly its depth. (A lone leaf has depth 0 and no path; this lesson gives it the one-bit code `0` by convention.) Frequent symbol, shallow leaf, short code — the trade the merge order was buying all along.

Why is the greedy merge safe? The swap argument: take any optimal tree and look at its two deepest sibling leaves. Swapping the two rarest symbols into those slots never increases the total — a rare symbol moving deeper costs less than a common symbol moving shallower saves. So *some* optimal tree merges the two rarest first, which is exactly the tree Huffman builds; apply the same argument after every merge and optimality follows by induction. That is the whole proof behind "provably optimal."

Ties matter more than they look. When two trees have equal weight, this lesson breaks the tie by creation order, which makes every run reproducible: the same text always builds the same tree. Any consistent tie-break yields an optimal code; different tie-breaks can build different trees with the same total bit count.

One honesty note about the picture: the animation draws the priority queue as a rack sorted left to right, because that is what a priority queue *means*. The Python code uses `heapq`, which stores the same queue as a clever array. If you want to see that array's internals, the heaps lesson is the place; here the rack keeps the greedy choice visible — the next merge is always the two leftmost trees.

## Huffman Coding Step by Step

The default input is `ABRACADABRA` — 11 characters, 5 distinct symbols.

1. **Count.** A appears 5 times, B twice, R twice, C once, D once.
2. **Build the queue.** Sorted by (frequency, arrival): `C(1) · D(1) · B(2) · R(2) · A(5)`.
3. **Merge 1.** Pop C(1) and D(1), hang them under a parent weighing 2. Three trees now weigh 2 — B, R, and the new [CD] — and creation order queues them as `B(2) · R(2) · [CD](2) · A(5)`.
4. **Merge 2.** Pop B(2) and R(2) into a parent weighing 4: `[CD](2) · [BR](4) · A(5)`.
5. **Merge 3.** Pop \[CD](2) and \[BR](4) into a parent weighing 6: `A(5) · [CDBR](6)`.
6. **Merge 4.** Pop A(5) and \[CDBR](6). The root weighs 11 — the whole text — and the tree is done.
7. **Assign codes.** Left is 0, right is 1. A sits one edge below the root: code `0`. Everything else lives three edges deep: C = `100`, D = `101`, B = `110`, R = `111`.
8. **Encode.** Walk the text symbol by symbol: `0 · 110 · 111 · 0 · 100 · 0 · 101 · 0 · 110 · 111 · 0` — 23 bits. A fixed-length code for 5 symbols needs ⌈log₂ 5⌉ = 3 bits each, 33 total. Huffman saved 30%, and every saved bit came from one place: A paid 1 bit instead of 3, five times over.

In the animation, the rack at the bottom is the priority queue; watch how every merge grabs the two leftmost trees, and how the amber `min pair` bracket never has to reach past them. The final beat draws both totals as bars — the green Huffman bar stopping short of the gray fixed-length one is the whole lesson in one frame. Both bars count payload only: a real compressed file also carries the code table, and on a text this short the table outweighs the savings (see Common Mistakes).

## Time and Space Complexity

| Phase | Cost |
| --- | --- |
| Counting frequencies | O(n) |
| Building the tree (k − 1 merges on a heap) | O(k log k) |
| Assigning codes | O(k) |
| Encoding | O(n) symbol lookups |

Total: **O(n + k log k)** time and O(k) space for a text of n characters over k distinct symbols, counting each codeword lookup as one operation. Writing the payload bit by bit or copying whole codewords also costs the output length and the summed codeword lengths; those variable-length strings are not free. There is no best or worst case in the usual sense — the merge count is always exactly k − 1 — but the *payoff* varies enormously, from a 30%+ saving on skewed text down to zero. The guarantee is one-sided: Huffman's payload never exceeds fixed-length's, and it beats it exactly when some prefix tree averages under ⌈log₂ k⌉ bits per symbol.

## Edge Cases

- **One distinct symbol.** The merge loop never runs; the tree is a single leaf with an empty path. This lesson's convention `path or "0"` gives it a one-bit code, so the payload is not empty. Another format could store the symbol and the text length instead, but it needs some explicit convention.
- **Two distinct symbols.** Each gets one bit no matter how skewed the frequencies are. One bit per symbol is Huffman's floor — it cannot charge A half a bit. (Arithmetic coding exists precisely to break this floor.)
- **The tie with fixed-length.** The Uniform scenario — four equally common symbols — builds a balanced tree where every code is 2 bits: Huffman *is* fixed-length, 24 against 24. But uniform and tied are not the same thing. Five equally common symbols still save (24 against 30, because ⌈log₂ 5⌉ rounds up to 3), and the skewed counts 3, 3, 2, 2 still tie at 20. The precise statement: Huffman ties fixed-length exactly when no prefix tree can average under ⌈log₂ k⌉ bits per symbol — and it never does worse.
- **Extreme skew.** Frequencies like 1, 2, 4, 8 build a vine: each merge hangs the whole previous tree one level deeper, and the rarest symbol's code stretches to k − 1 bits. The total still beats fixed-length — the Skewed scenario shows 25 against 30.
- **Ties.** Equal weights are broken by creation order, so the trace is deterministic. A different consistent tie-break may build a different tree, but never a different total.

## Common Mistakes

- **Sorting the symbols once and pairing them up in order.** The merged parent must go *back into the queue* and compete at its new weight. Skip the re-insert and you build a lopsided tree that is no longer optimal.
- **Assigning short codes by frequency rank directly** — "most frequent symbol gets `0`, next gets `1`, next gets `01`…" — without a tree. You will almost certainly produce a code where one codeword prefixes another, and the decoder cannot tell "that symbol" from "keep reading".
- **Forgetting the single-symbol text.** An empty path cannot record how many times the symbol repeats. This lesson needs `path or "0"`; another format must store the length some other way.
- **Shipping the bits without the table.** The codes depend on this text's frequencies; the decoder needs the tree (or the frequency table) to rebuild them. Compressed size honestly includes that header — on an 11-character text the header outweighs the savings, which is why Huffman earns its keep on kilobytes, not on `ABRACADABRA`.
- **Breaking ties inconsistently.** Popping equal-weight nodes in a nondeterministic order still yields an optimal total, but the encoder and a decoder that rebuilds the tree from frequencies may disagree about which optimal tree — and decode garbage.