Huffman coding gives frequent symbols short codes and rare symbols long ones, so the total number of bits is as small as possible for a code where no codeword is the prefix of another. Building the code is a short greedy loop, and the classic example from Introduction to Algorithms (CLRS) shows every step.
The input: a file of 100 characters using six symbols with these frequencies:
| Symbol | a | b | c | d | e | f |
|---|---|---|---|---|---|---|
| Frequency | 45 | 13 | 12 | 16 | 9 | 5 |
The algorithm
Put every symbol in a priority queue by frequency. Then repeat until one tree is left:
- Take out the two smallest nodes.
- Make a new node whose frequency is their sum, with them as its children.
- Put the new node back.
Building the tree
| Step | Merge | New node |
|---|---|---|
| 1 | f (5) + e (9) | 14 |
| 2 | c (12) + b (13) | 25 |
| 3 | 14 + d (16) | 30 |
| 4 | 25 + 30 | 55 |
| 5 | a (45) + 55 | 100 (the root) |
After step 1 the queue holds c 12, b 13, 14, d 16, a 45; the two smallest are c and b, and so on. Each merge always takes the two smallest values available right now, whether they are original symbols or merged nodes.
Reading off the codes
Label every left branch 0 and every right branch 1, then read the path from the root to each symbol:
| Symbol | Frequency | Code | Bits used |
|---|---|---|---|
| a | 45 | 0 | 45 × 1 = 45 |
| c | 12 | 100 | 12 × 3 = 36 |
| b | 13 | 101 | 13 × 3 = 39 |
| d | 16 | 111 | 16 × 3 = 48 |
| f | 5 | 1100 | 5 × 4 = 20 |
| e | 9 | 1101 | 9 × 4 = 36 |
| total | 224 bits |
A fixed-length code for six symbols needs 3 bits each: 100 × 3 = 300 bits. Huffman saves 76 bits, about 25%.
The average code length is 224 ÷ 100 = 2.24 bits per symbol.
Decoding
Because no code is a prefix of another, you can decode without separators: read bits until they match a code, output the symbol, repeat. 0 101 1101 0 decodes as a, b, e, a.
Different trees, same answer
When two nodes have equal frequency, or you put the smaller one on the right instead of the left, you get a different-looking tree and different codes. The total number of bits is the same for every valid Huffman tree, so exam answers with different codes can all be correct. If your course requires a convention (for example, the smaller node always on the left), follow it.
Common mistakes
- Merging the wrong pair after the first step: always compare the merged nodes with the remaining symbols.
- Reading codes from the leaves upwards. Codes are read from the root down.
- Forgetting to multiply by frequency when asked for total bits.
- Using ⌈log₂ n⌉ wrongly for the fixed-length comparison. Six symbols need 3 bits (2³ = 8 ≥ 6), not 2.
Try it
The Huffman coding calculator builds the tree for your own frequencies or text, shows every merge, lists the codes, and compares the total with a fixed-length code. For the analysis side of an algorithms course, the master theorem calculator solves divide-and-conquer recurrences.
For a related walkthrough, read Master Theorem: 10 Solved Examples.