Given a message and how often each symbol in it occurs, build a binary code — a bit pattern per symbol — that makes the whole encoded message as short as possible, with the constraint that no symbol's code may be a prefix of another symbol's code (so a decoder reading bit by bit always knows the instant a code is complete, no separators required). The greedy idea is almost embarrassingly simple: repeatedly take the two least-frequent nodes available — starting with one leaf per symbol — and merge them into a new internal node whose frequency is their sum, until only one node, the root, remains. Reading root to leaf, "go left" contributes a 0 bit and "go right" contributes a 1 bit, so a frequent symbol that got merged in early ends up shallow with a short code, and a rare symbol that survived many rounds unmerged ends up deep with a long one.
This is the site's first entry filed under a dedicated Greedy category, though not its first greedy algorithm — Kruskal's and Prim's algorithms already commit to "cheapest available option, never reconsidered" under Minimum Spanning Trees. What makes Huffman coding worth a category of its own is that the greedy choice here is provably always correct — one of a comparatively short list of problems where that's true. 0/1 Knapsack's own Pitfalls section already showed the opposite outcome on a different problem: picking items by value-density, the locally obvious greedy move, lands on a genuinely worse pack than the DP table finds. Greedy is a strategy, not a guarantee — Huffman coding is one of the good cases.
The category no longer holds just one entry — Activity Selection joined it with its own provably-correct greedy rule and its own exchange-argument proof, plus a live demonstration of two other locally-plausible rules that aren't safe on the same data, worth a look for the same "greedy is a strategy, not a guarantee" reason this paragraph just made.
Type a message and press Load, then Step or Run. Each step pulls the two lowest-frequency items out of the queue below — ties broken by which symbol was merged or first seen earliest — and merges them into one new node, drawn onto the growing tree with its two edges labeled 0 (left) and 1 (right). Once every node has merged into a single root, the codes are read straight off the tree and the actual bit savings over a fixed-width baseline are shown.
priority queue (lowest frequency first)
The greedy choice — always merge the two rarest items right now — is safe because of a fact about optimal prefix codes that can be proven directly: in any optimal code, the two least-frequent symbols are always siblings at the deepest level of the tree (if they weren't, swapping them with whichever symbols are at the deepest level can only shorten the total encoding, never lengthen it, so an arrangement that violates this was never optimal to begin with). Once that's established, merging those two into a single combined-frequency node and recursing is exactly correct: solve the smaller problem optimally, and the two lowest-frequency symbols end up exactly where the proof says they must. This is the same shape of argument Kruskal's algorithm uses for the cut property — a local greedy fact, proven once, that composes into a global optimum without ever needing to look ahead or backtrack.
On the default message abracadabra (11 characters: a×5, b×2,
r×2, c×1, d×1), four merges run: c+d
→ 2, b+r → 4, those two combined → 6, and finally a + that
6-node → the 11-node root. The resulting codes are a=0 (1 bit),
b=110, r=111, c=100,
d=101 (3 bits each) — encoding the whole message in 23 bits.
A fixed-width code over 5 distinct symbols needs ⌈log₂5⌉ = 3 bits per character
regardless of frequency, so 11 characters would cost 33 bits fixed-width — Huffman
coding saves 10 bits, 30.3%, by giving the far more common a a
below-average-length code and paying for it with above-average-length codes on the rare symbols. The
message's own Shannon entropy — the theoretical fewest bits any code could average per symbol,
computed independently from the same frequencies — works out to about 2.04 bits/symbol, 22.44 bits
total; Huffman's actual 23 bits (2.09 bits/symbol) lands within one bit of that lower bound, which is
the standard guarantee: Huffman coding is always within 1 bit per symbol of entropy, and exactly
matches it when every frequency happens to be an exact power of one-half.
function huffman(message) {
const freq = new Map();
for (const ch of message) freq.set(ch, (freq.get(ch) || 0) + 1);
let nextId = 0;
let queue = [...freq.entries()].map(([sym, f]) =>
({ id: nextId++, freq: f, sym, left: null, right: null }));
// A real implementation uses a binary heap (see Binary Heap) for O(log n)
// extract-min; this sorts the small array fresh each round for clarity.
const byFreqThenId = (a, b) => a.freq - b.freq || a.id - b.id;
while (queue.length > 1) {
queue.sort(byFreqThenId);
const a = queue.shift(), b = queue.shift();
queue.push({ id: nextId++, freq: a.freq + b.freq, sym: null, left: a, right: b });
}
const root = queue[0];
const codes = {};
if (root.sym !== null) {
codes[root.sym] = '0'; // only one distinct symbol — see Pitfalls
} else {
(function walk(node, path) {
if (node.sym !== null) { codes[node.sym] = path; return; }
walk(node.left, path + '0');
walk(node.right, path + '1');
})(root, '');
}
return codes;
}Ties don't change the total length, only which symbol gets which code. Two
symbols tied on frequency can be merged in either order, and different implementations legitimately
break ties differently. Checked directly: re-running the exact same input with the tie-break rule
reversed (preferring the more-recently-created node instead of the earlier one) produces a visibly
different tree — b ends up with a 2-bit code instead of 3, c and
d both end up with 4-bit codes instead of 3 — but the total encoded length comes out to
the identical 23 bits either way. An optimal prefix code isn't unique; its total length is.
One distinct symbol has no merge to run at all. Type a message with only one
repeated character — aaaa, say — and the queue starts and ends with a single leaf: there
is nothing to merge, so the tree-building loop this demo relies on never executes. The
information-theoretically "optimal" code for a single symbol is zero bits per occurrence (there's
never any uncertainty to resolve), but a real bitstream can't represent a zero-length code — there
would be no way to tell how many times it occurred. This demo assigns the single symbol a 1-bit code
(0) by the same convention any real implementation needs, not something the greedy merge
logic derives on its own.
The impressive-sounding compression ratio depends on a fair baseline. It's tempting
to compare Huffman's 23 bits against 8-bit ASCII (11 × 8 = 88 bits) and claim a 74% reduction, but
that conflates two separate savings: most of it comes from only needing 5 symbols' worth of alphabet,
not 256, which any fixed-width code already captures by using ⌈log₂5⌉ = 3 bits instead of
8. The fair comparison — fixed-width code over the same alphabet — is 33 bits, and Huffman's
real win over that fair baseline is the 30.3% shown above, entirely from exploiting the skew in
symbol frequency, which is the one thing a fixed-width code can never do regardless of alphabet
size.
The code table itself has to be transmitted or agreed on in advance. A decoder can't reconstruct symbol-to-code mappings from the bitstream alone — it needs the tree (or an equivalent description of it) too. For a short message like this session's 11-character example, that overhead is real and un-amortized; Huffman coding pays off once the message is long enough, or the table is reused across many messages, that the tree's cost is small next to what it saves.
Time: with a proper binary heap for extract-min, building the tree costs
O(n log n) for n distinct symbols — n−1 merges, each a
constant number of O(log n) heap operations. Encoding a message of length L
is O(L), one code-table lookup per character; decoding a bitstream of B bits
is O(B), one root-to-leaf pointer hop per bit, since the total hops across a full decode
never exceed the bit count. This demo re-sorts a small array every round instead of maintaining a
heap, which is fine for a handful of symbols but wouldn't scale the way a real implementation's
Binary Heap-backed queue does. Space:
O(n) — a binary tree with n leaves has exactly n−1 internal
nodes, plus the O(n) code table itself.
See Choosing a Greedy Strategy for how this entry's proof compares against the site's other nine Greedy entries — short version: this is Tier 1, exact on every input, by a structural exchange argument rather than a swap between two named items.