4.3Huffman coding
The idea
Huffman coding builds the best prefix code by repeatedly merging the two rarest symbols.
Think of it like this: Giving the shortest nicknames to the most talked-about people.
Why it exists
It combines greedy ideas with heaps; GATE asks code lengths and total bits.
How it works
- Put all symbols in a min-heap by frequency.
- Remove the two smallest and merge them into one node.
- Repeat until one node remains (n − 1 merges).
- Left edge 0, right edge 1: the path is the code.
Worked example: a:45 b:13 c:12 d:16 e:9 f:5
Merge f, e → 14; c, b → 25; 14, d → 30; 25, 30 → 55; 45, 55 → 100. Codes: a = 0 (1 bit), b, c, d are 3 bits, e, f are 4 bits. Total 224 bits against 300 for a fixed 3-bit code.
Now play with it
- →Press "Next step" to watch the merges.
- →Change the frequencies so two are equal and compare the totals.
- merge f(5) and e(9) → 14
- merge c(12) and b(13) → 25
- merge fe(14) and d(16) → 30
- merge cb(25) and fed(30) → 55
- merge a(45) and cbfed(55) → 100
| symbol | frequency | code | bits |
|---|---|---|---|
| a | 45 | 0 | 45 |
| d | 16 | 111 | 48 |
| b | 13 | 101 | 39 |
| c | 12 | 100 | 36 |
| e | 9 | 1101 | 36 |
| f | 5 | 1100 | 20 |
Greedy choice: always merge the two least frequent nodes. Ties can give different trees but the same total cost. n symbols need n − 1 merges: O(n log n) with a heap.
Check yourself
A Huffman code is built for 8 symbols. The number of merge steps is
Exam notes (the dense version)
Build an optimal prefix code: repeatedly merge the two least frequent nodes. n symbols need n − 1 merges; O(n log n) with a min-heap. Frequent symbols get short codes. The total cost is Σ frequency × code length, which equals the sum of all internal-node weights. No code is a prefix of another, so decoding is unambiguous.
Previous year questions: Algorithm Design: Divide & Conquer, Greedy, DP (7)
PYQs are grouped by topic, so this is the full set for Algorithm Design: Divide & Conquer, Greedy, DP; try the ones that match this subtopic. Open all 7 on the topic page.