AlgoScope

Huffman Coding

Repeatedly merge the two least frequent symbols. The merge tree gives prefix-free codes.

Greedy, algorithm, intermediate
Merging c:1 and d:1.a:5b:2c:1d:1r:2
Merging c:1 and d:1.a:5b:2c:1d:1r:2

Huffman Coding: The classic: five characters, very skewed

Decision, step 2 of 15

There are 5 roots: c:1, d:1, b:2, r:2, a:5. The two lightest are c:1 and d:1, so they merge. Burying a root one level deeper costs one extra bit for every character under it, which is why the lightest go first.

Cost

Best
O(n log n)
Average
O(n log n)
Worst
O(n log n)
Space
O(n)