~/home/frequent symbols, short codes: huffman coding
Algorithm · Greedy
Frequent Symbols, Short Codes.
Don't memorize Huffman coding — watch the tree assemble itself. To compress text you want frequent symbols to have short codes and rare ones long codes, with no code a prefix of another so the bitstream decodes cleanly. Huffman builds the optimal such code greedily: repeatedly merge the two least-frequent nodes with a min-heap until a single tree remains, then read each code off its root-to-leaf path.
prefix-free · merge the two smallest · min-heap · left 0 / right 1
PREFIX-FREE
No code is a prefix of another, so a stream of bits decodes with no separators.
FREQUENCY
Common symbols deserve short codes; rare ones can afford to be long.
GREEDY MERGE
Combine the two lowest-frequency nodes into a parent; repeat. A min-heap finds them fast.
READ THE TREE
Walk from the root: left is 0, right is 1. Each leaf's path is its code.
huffman.sim — a:5, b:2, c:1, d:1
Ready
Four symbols with frequencies a:5, b:2, c:1, d:1. Each starts as a leaf. Press Step to greedily merge the two lowest-frequency nodes, over and over, until one tree remains — then read the codes.
merge the two smallest weights → parent weight = sum · repeat
0
Merges
—
Encoded bits
Greedy, and provably optimal
Most greedy algorithms give a decent answer that is not always the best. Huffman is the rare greedy that is provably optimal. Start with one leaf per symbol, weighted by frequency, all sitting in a min-heap. Pull the two smallest, join them under a new parent whose weight is their sum, and drop that parent back in the heap. Repeat until a single tree remains. Why is grabbing the two smallest each time optimal? An exchange argument: in any optimal prefix code the two least-frequent symbols can be moved to be the two deepest sibling leaves without increasing the cost — so building them in as the first, deepest merge never closes off the best solution. The resulting tree minimizes the total encoded length, the sum of each frequency times its depth. For a:5, b:2, c:1, d:1 that comes to just 15 bits versus 18 for a flat two-bit code.
01
One leaf per symbol
Weight each symbol by its frequency and put them all in a min-heap (a priority queue).
02
Merge the two smallest
Pop the two lowest weights, join them under a parent of weight = their sum, push it back.
03
Repeat to one tree
Each merge removes two nodes and adds one, so after n−1 merges a single tree is left.
04
Read the codes
Label edges 0 (left) and 1 (right); each leaf's path is its codeword. Total bits = Σ freq·depth.
Time
O(n log n)
Space
O(n)
Result
Optimal prefix code
Engine
Greedy + heap
Because only leaves hold symbols, every codeword ends at a leaf and can never begin another — that is the prefix-free property, for free. Huffman is the entropy-coding stage inside DEFLATE (zip, gzip, PNG), JPEG and MP3. It leans directly on the priority queue to keep pulling the smallest, and it sits beside Kruskal and Dijkstra in the greedy family — take the locally best choice, and here that choice is provably globally best.
Check yourself
1 · What does Huffman merge at each step?
Popping the two smallest weights from a min-heap and joining them pushes the rarest symbols deepest, which is exactly what an optimal code needs.
2 · Why must the code be prefix-free?
If no codeword is a prefix of another, the decoder knows a symbol is complete the moment its bits end — only leaves carry symbols, so this always holds.
3 · Why is Huffman's greedy choice optimal?
You can rearrange any optimal code so the two least-frequent symbols are deepest siblings without raising the cost, so merging them first never loses optimality.
Questions
Huffman vs a fixed-width code?
A fixed-width code uses ⌈log₂ k⌉ bits for every symbol. Huffman gives shorter codes to frequent symbols, so when the frequencies are skewed the average length drops — and it is the optimal prefix code with whole-bit codewords. For a:5, b:2, c:1, d:1 it needs 15 bits instead of 18.
Where is it actually used?
As the entropy-coding stage in DEFLATE (zip, gzip, PNG), JPEG and MP3. The earlier stages model or transform the data; Huffman (or a close relative) squeezes the final symbol stream.
Can you beat Huffman?
Only by leaving whole-bit codewords behind. Arithmetic and range coding assign effectively fractional bits per symbol and can compress slightly better, at more computational cost. Among integer-length prefix codes, Huffman is optimal.
The greedy that is always right.
Merge the two rarest, over and over, until one tree stands — then read the codes off its branches. Provably the shortest prefix code there is.