Huffman Coding

Fixed-width encoding spends the same number of bits on every character, which is wasteful: an e that appears constantly costs as much as a z that barely shows up. Huffman coding fixes that by giving frequent characters short bit-codes and rare ones long codes. The result is the *optimal* prefix code — no scheme of unambiguous bit-strings encodes that text in fewer bits.

Why prefix-free matters

A prefix code is one where no character's code is the start of another's. That property lets the decoder read a bitstream left to right and know exactly where each character ends — no separators needed. Huffman codes are prefix-free automatically because every character sits at a leaf of a binary tree, and no leaf is on the path to another leaf.

The algorithm

1. 1Make one leaf node per character, weighted by its frequency, and put them all in a min-heap.
2. 2Pop the two smallest trees. Make a new internal node whose frequency is their sum, with those two as its children. Push it back.
3. 3Repeat until one tree remains — the Huffman tree.
4. 4Read each character's code by walking root → leaf: left = 0, right = 1.

Worked example

Frequencies: f:5, e:9, c:12, b:13, d:16, a:45. Watch the heap merge the two smallest each round (the new parent's frequency is shown in parentheses):

start: f5  e9  c12  b13  d16  a45
merge f5 + e9   -> (14)   : c12 b13 (14) d16 a45
merge c12 + b13 -> (25)   : (14) d16 (25) a45
merge 14 + d16  -> (30)   : (25) (30) a45
merge 25 + 30   -> (55)   : a45 (55)
merge a45 + 55  -> (100)  : one tree -> done

resulting codes:  a = 0      (1 bit, most frequent)
                  c = 100    d = 111
                  b = 101    e = 1101   f = 1100

The most common symbol a gets a 1-bit code, while the rarest f gets 4 bits. Total cost is the sum over symbols of frequency × code length — strictly fewer bits than any fixed-width or alternative prefix scheme for these frequencies.