Huffman Coding
Given symbols with their frequencies, construct a binary prefix code that minimises the total encoded length Σ frequency × code length. Return the minimum total length (or the codes themselves).
- 2 ≤ number of symbols ≤ 10^5
- 1 ≤ frequency ≤ 10^9
- Repeatedly combine the two smallest weights
- Each merge cost is added to the total
- Priority queue drives the greedy
When you repeatedly need the minimum or maximum of a changing collection, a heap gives O(log n) insert and extract instead of re-sorting. "Top k" problems keep a heap of size k for O(n log k); a "median of stream" balances a max-heap of the lower half against a min-heap of the upper half.
Push all frequencies into a min-heap. Repeatedly pop the two smallest, add their sum to the running total (that sum is the extra bit every symbol in the merged subtree pays), and push the sum back as a new internal node. Stop when one node remains. Merging the two least frequent symbols first is optimal because the deepest leaves of an optimal tree can always be swapped to be the two rarest symbols.
- With frequencies pre-sorted, two queues replace the heap for O(n). Arithmetic coding beats Huffman for skewed distributions but is not a prefix code.