Huffman Coding
Repeatedly merge the two least frequent symbols. The merge tree gives prefix-free codes.
Huffman Coding: The classic: five characters, very skewed
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)