GreedyAlgorithmaka Huffman tree, optimal prefix code, minimum weighted path length

Huffman Coding

Build an optimal prefix-free binary code by repeatedly merging the two least frequent symbols with a min-heap.

Pattern: Heap / Priority QueuePractice (3)
Progress

Overview

Given symbol frequencies, Huffman coding produces a prefix-free binary code (no codeword is a prefix of another) that minimizes the total encoded length Σ f_i · len_i. The greedy step: take the two least frequent nodes, merge them into a parent whose frequency is their sum, and repeat until one tree remains. Left edges are 0, right edges are 1; each symbol's code is the path from the root.

It is the prototypical greedy with a [[priority-queue]]: n − 1 merges, each an O(log n) extract-min pair and insert. Huffman codes are optimal among symbol-by-symbol codes and sit inside DEFLATE (zip, PNG), JPEG, and MP3.

greedypriority queuecompressionprefix codebinary treeexchange argument

Intuition

A mental model before the formal terms.

You are assigning Morse-like codes: frequent letters deserve short codes, rare ones can afford long ones. Building the tree bottom-up, the two rarest symbols are the ones you can most afford to push deepest — make them siblings at the bottom, treat their pair as one new "symbol" with the combined frequency, and repeat.

Prefix-free means the decoder never needs a separator: walk the tree from the root bit by bit; when you hit a leaf, emit that symbol and jump back to the root.

How it works

  1. Create a leaf for each symbol with its frequency and push all leaves into a min-heap keyed by frequency.
  2. While the heap has more than one node: pop the two smallest a, b; create an internal node with frequency a.f + b.f and children a, b; push it.
  3. The last node is the root. Traverse it, appending 0 for left and 1 for right, to obtain each leaf's codeword.
  4. Encoding is table lookup; decoding walks the tree. The tree (or code lengths) must be transmitted with the data.

Why it works

Greedy-choice property (exchange). In any optimal tree, the two least frequent symbols x, y can be made sibling leaves at maximum depth: take any two deepest siblings a, b in an optimal tree and swap x↔a, y↔b. Since f_x ≤ f_a and f_y ≤ f_b, and x, y move to depth ≥ their old depth while a, b move up, the cost Σ f · depth does not increase. So some optimal tree has x and y as siblings — exactly what the first merge produces.

Optimal substructure. Replace the sibling pair x, y by a single symbol z with f_z = f_x + f_y. Any tree T for the original alphabet with x, y as siblings has cost cost(T') + f_x + f_y where T' is the tree for the reduced alphabet. Minimizing cost(T) therefore equals minimizing cost(T'), and induction on the alphabet size finishes the proof.

Prefix-freeness is automatic because symbols are leaves: no leaf is an ancestor of another, so no codeword is a prefix of another.

Recognition

How to tell a problem wants this.

  • "Minimize total cost where cost = Σ weight × depth" — file compression, but also minimum cost to merge files / ropes / stones when the merge cost is the sum (the merge order is a Huffman tree).
  • "Prefix-free code", "variable-length encoding", "optimal binary tree for given leaf weights".
  • A heap-based loop that repeatedly combines the two smallest items.
“k most frequent” → Heap / Priority Queue“maximum number of non-overlapping” → Greedy

Interactive visualization

Play, step, change the input. ← → and space work too.

No interactive visualization for this topic yet

Related visualizations are linked under Related.

Pseudocode

1heap = min-heap of leaves (freq, symbol)
2while len(heap) > 1:
3  a = pop(heap); b = pop(heap)
4  push(heap, node(freq = a.freq + b.freq, left = a, right = b))
5root = pop(heap)
6assign codes: dfs(root, prefix): left -> prefix + "0", right -> prefix + "1"

Implementations

1import heapq
2from typing import Optional
3 
4# Huffman coding: build an optimal prefix-free code by repeatedly merging the
5# two least frequent symbols. The greedy choice is provable — the two rarest
6# symbols can always be placed as siblings at the deepest level.
7 
8 
9class HuffNode:
10    __slots__ = ("symbol", "freq", "left", "right")
11 
12    def __init__(self, symbol: Optional[str], freq: int,
13                 left: Optional["HuffNode"] = None, right: Optional["HuffNode"] = None) -> None:
14        self.symbol = symbol  # None on internal nodes
15        self.freq = freq
16        self.left = left
17        self.right = right
18 
19 
201 · A min-heap ordered by frequency; ties broken by insertion order
21def build_tree(freq: dict[str, int]) -> Optional[HuffNode]:
22    # the tie-breaker is essential: HuffNode is not comparable, so a frequency
23    # tie would make heapq try to compare two nodes and raise TypeError
24    heap = [(f, i, HuffNode(sym, f)) for i, (sym, f) in enumerate(freq.items())]
25    heapq.heapify(heap)
26    if not heap:
27        return None
28    tie = len(heap)
29 
302 · Merge the two rarest into a parent whose frequency is their sum
31    while len(heap) > 1:
32        f1, _, a = heapq.heappop(heap)
33        f2, _, b = heapq.heappop(heap)
34        heapq.heappush(heap, (f1 + f2, tie, HuffNode(None, f1 + f2, a, b)))
35        tie += 1
36    return heap[0][2]
37 
38 
393 · Walk the tree: left appends 0, right appends 1
40def collect_codes(node: Optional[HuffNode], prefix: str = "",
41                  out: Optional[dict[str, str]] = None) -> dict[str, str]:
42    if out is None:
43        out = {}
44    if node is None:
45        return out
46    if node.left is None and node.right is None:
47        # A single-symbol alphabet still needs one bit, hence the empty-prefix case
48        out[node.symbol] = prefix or "0"
49        return out
50    collect_codes(node.left, prefix + "0", out)
51    collect_codes(node.right, prefix + "1", out)
52    return out
53 
54 
554 · The codes are prefix-free, so decoding needs no separators
56def encode(text: str, codes: dict[str, str]) -> str:
57    return "".join(codes[c] for c in text)
58 
59 
605 · Total encoded length = sum over symbols of freq * codeLength
61def encoded_bits(freq: dict[str, int], codes: dict[str, str]) -> int:
62    return sum(f * len(codes[sym]) for sym, f in freq.items())
Walkthrough
  1. The tie-breaker in (f, i, node) is *load-bearing*: HuffNode defines no __lt__, so on a frequency tie heapq would try to compare two nodes and raise TypeError. This is the single most common Huffman bug in Python.
  2. heapq.heapify(heap) builds the initial heap in O(k) rather than k pushes at O(k log k).
  3. out: Optional[dict] = None with if out is None: out = {} is the correct mutable-default idiom — a literal {} default would be shared across every call to the function.
  4. prefix or "0" uses the falsiness of the empty string to supply the single-symbol code, which is idiomatic but worth the comment.
  5. "".join(...) over a generator is the efficient string build; repeated += would be quadratic for a long text.
Complexity (this implementation)
time O(k log k) for k distinct symbols · space O(k) nodes
Language notes
  • heapq compares tuples element by element and falls through to later elements on a tie, which is exactly why a non-comparable payload must be preceded by a unique tie-breaker.
  • A mutable default argument (out: dict = {}) is evaluated once at definition time and shared by every call — the classic Python gotcha, avoided here with the None sentinel.
  • collections.Counter(text) builds the frequency table in one call.
  • __slots__ on HuffNode avoids a per-instance __dict__, which matters for a large alphabet.
Common mistakes in this language
  • Pushing (freq, node) without a tie-breaker and hitting TypeError: '<' not supported between instances of 'HuffNode' — but only when two frequencies happen to tie, so it passes small tests.
  • Using out: dict = {} as a default and accumulating codes across calls.
  • Building the encoded string with += in a loop instead of "".join.
Language differences that matter here
  • The non-comparable-payload problem is sharpest in Python, where a frequency tie makes heapq compare two HuffNodes and raise TypeError — the tie-breaker is mandatory, not stylistic. C++ and JS/TS need an explicit comparator anyway, so the issue surfaces at design time instead.
  • Ownership: C++ must decide between unique_ptr juggling, shared_ptr, or an arena, while JS/TS and Python simply let the collector handle a tree that is built once and discarded.
  • Heap construction from a full list is O(k) in Python (heapify) and C++ (make_heap), and O(k log k) in JS/TS where each element must be pushed individually.
  • Mutable default arguments are a Python-only hazard: the out=None sentinel here has no counterpart in the other three, where default parameters are re-evaluated per call.

Complexity

Best
—
Average
—
Worst
O(n log n)
Space
O(n)

n symbols, n − 1 merges of O(log n) each. O(n) if frequencies arrive sorted (two-queue method). Tree has 2n − 1 nodes.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Symbol-by-symbol lossless compression with a known frequency table.
  • Any "merge two smallest, cost is their sum" problem: minimum cost to connect ropes, merge sorted files, combine stones with sum cost.
  • Constructing an optimal-depth tree for weighted leaves (alphabetic order not required).
Avoid it when
  • Symbols must keep their order (alphabetic / optimal BST): Huffman reorders leaves freely. Weights [1, 10, 1] in fixed order: Huffman would merge the two 1s first, but they are not adjacent, so the tree is invalid — use the O(n²) Garsia–Wachs / Interval (Range) DP optimal BST DP.
  • Merge cost is not the sum (e.g. max, or cost depends on position): the exchange argument relies on cost = Σ weight × depth. Stone merging where only adjacent piles merge is Interval (Range) DP (Minimum Cost to Merge Stones), not Huffman.
  • Streaming data with unknown or drifting frequencies — use adaptive Huffman or arithmetic coding; arithmetic coding also beats Huffman when a symbol has probability well above 0.5 (Huffman cannot use fewer than 1 bit per symbol).

Alternatives

Interval (Range) DPPriority QueueTrie

Common mistakes

  • Forgetting the single-symbol edge case (the root is a leaf; it needs a 1-bit code, not an empty one).
  • Pushing a tuple (freq, node) into Python's heap without a tiebreaker — comparing nodes raises TypeError on equal frequencies.
  • Assuming Huffman output is unique; ties can be broken differently, yielding different but equally optimal codes.
  • Building the tree top-down by splitting frequencies in half (Shannon–Fano) — that is not optimal.

Interview patterns

  • Minimum Cost to Connect Sticks / Ropes: pure Huffman with a heap, return the sum of merge costs.
  • Explain the two-part proof (siblings lemma + reduction) — the interviewer wants the exchange argument, not just the algorithm.
  • Decoding with a trie of codewords; encoding via a lookup table.
Interview questions on this
Mock interviews

Example problems

Merge k Sorted ListshardTask SchedulermediumHuffman Codingmedium