Huffman Coding

Build an optimal prefix-free binary code by repeatedly merging the two least frequent symbols. Greedy is optimal via the greedy choice and optimal substructure.

Algorithm Steps

Initialize a min-heap with character frequencies.
Extract two smallest, merge into a new node.
Insert merged node back, repeat until one node left.
Assign 0/1 along left/right edges to get codes.

Speed (ms)

Symbols (editable)

Min-Heap Levels

Press Run to start merging smallest frequencies.

Pseudocode

1procedure HUFFMAN(freqs)
2  create min-heap Q from freqs
3  while |Q| > 1 do
4    x ← extract-min(Q)
5    y ← extract-min(Q)
6    z ← new node with freq = x.freq + y.freq
7    z.left ← x; z.right ← y
8    insert(Q, z)
9  end while
10  return extract-min(Q) // root of tree
11end procedure

Practice Problems

Use Cases

Lossless compression (ZIP, GZIP, DEFLATE stages).
Compression in image formats (e.g., JPEG entropy coding).
Efficient prefix-free encoding in compilers and data transfer.

Back to Fractional Knapsack Next: Job Scheduling