1. One-Liner
Huffman coding merges the two smallest frequency nodes until one tree remains, yielding a minimum expected codeword length for a given symbol distribution (prefix-free).
2. The Problem It Solves
Symbols appear with known frequencies. Assign binary codes so frequent symbols get shorter bitstrings, no code is a prefix of another, and average bits per symbol is minimized.
3. The Core Idea
Always combine the two lightest pieces—locally optimal merges build a globally optimal tree (Kraft–McMillan + greedy proof). Like merging piles of paper: smallest piles first keeps depth balanced for heavy items near the root.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1. Leaves | Each symbol is a node with its weight |
| 2. Min-heap | Insert all nodes by frequency |
| 3. Merge | Pop two mins, create parent with sum weight, push back |
| 4. Repeat | Until one node remains—the Huffman tree |
| 5. Codes | Label edges 0/1; read leaf paths |
5. Dry Run Example
Frequencies A:5, B:9, C:12, D:13, E:16, F:45. Repeatedly merge smallest pairs; frequent F ends up shallow (short code), rare symbols deeper.
6. Key Properties
| Property | Value |
|---|---|
| Optimal | For fixed frequencies & binary alphabet |
| Prefix-free | Valid codewords from leaves |
| Greedy | Two smallest combine |
7. Where It Is Used
| Domain | Use |
|---|---|
| Compression | DEFLATE family, historical file compressors |
| Theory | Entropy, coding bounds |
8. Interview Tips
Mention min-heap, O(n log n) build, tie-breaking doesn’t break optimality, contrast with fixed-length codes and arithmetic coding.
9. Comparison with Other Approaches
| Approach | Avg length | Notes |
|---|---|---|
| Huffman | Near entropy | Integer bit lengths per symbol |
| Fixed 8-bit | Worse | No adaptation |
| Arithmetic | Can beat Huffman per symbol | Fractional bits |
10. Complexity
| Metric | Value |
|---|---|
| Time | O(n log n) with n symbols (heap ops) |
| Space | O(n) for tree and heap |
Implementation Example (PYTHON)
import heapq
def huffman_tree(freq):
heap = [[w, [sym, '']] for sym, w in freq.items()]
heapq.heapify(heap)
while len(heap) > 1:
lo = heapq.heappop(heap)
hi = heapq.heappop(heap)
for p in lo[1:]:
p[1] = '0' + p[1]
for p in hi[1:]:
p[1] = '1' + p[1]
heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
return heap[0][1:]