Huffman Coding Explained: Why Merging the Two Rarest Symbols Works

A fixed-width code spends the same number of bits on every symbol. English text does not use every letter equally, so that is wasteful: the common letters should be cheap and the rare ones can afford to be expensive. Huffman coding finds the best way to do that, and it does it with one of the simplest greedy rules in the curriculum: merge the two rarest things, repeat.

The problem it solves

Given each symbol's frequency, assign every symbol a binary codeword so that:

• the code is prefix-free, meaning no codeword is the start of another, so a bit stream decodes without separators, and
• the total encoded length, the sum of frequency × codeword length, is as small as possible.

For the lesson's counts, a: 7, b: 4, c: 3, d: 2, a fixed 2-bit code costs 16 × 2 = 32 bits. The question is how low a prefix-free code can go.

The intuition

A prefix-free code is a binary tree. Symbols sit at the leaves, and a symbol's codeword is the path from the root, 0 for left and 1 for right. The codeword length is the leaf's depth, so the goal is: frequent symbols shallow, rare symbols deep.

Huffman builds that tree from the bottom. Put every symbol in a min-heap keyed by count. Pop the two smallest, join them under a new parent whose count is their sum, and push the parent back. When one node remains, it is the root.

Why the sum? Every merge pushes everything below the new parent one level deeper, which adds one bit to every occurrence of those symbols. That is exactly the parent's count. So the encoded size equals the sum of all merged counts, and the lesson's heap loop computes it without building a tree at all.

Why is greedy safe? Two facts, both provable by swapping leaves:

• In some optimal tree, the two rarest symbols are siblings at the deepest level. If a more frequent symbol sat deeper, swapping it with a rarer one could only shorten the total.
• Once those two are glued into one pseudo-symbol, what remains is the same problem with one symbol fewer, and the glued pair costs the same extra amount in any tree.

So the first greedy choice never rules out an optimal answer, and induction does the rest.

Watch it run

The animation starts from the four leaves, a 7, b 4, c 3 and d 2. First d and c merge into a 5, then b and that 5 into a 9, then a and the 9 into the root, 16. The leaves never move, so each merge visibly pushes the symbols below it one level down. The last frame labels the edges 0 and 1, and the codes can be read off: a gets one bit and c and d get three.

The code

A full encoder. The counter in each heap entry is a tie-breaker: without it, two equal counts would make Python compare the payloads, and a string cannot be compared with a tuple:

import heapq
from collections import Counter
from itertools import count

def huffman_codes(freq):
    """freq: dict symbol -> count. Returns dict symbol -> bit string."""
    if len(freq) == 1:                         # one symbol still needs a bit
        return {sym: "0" for sym in freq}
    tick = count()                             # tie-breaker: never compare trees
    heap = [(f, next(tick), sym) for sym, f in freq.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        f1, _, left = heapq.heappop(heap)      # the two rarest
        f2, _, right = heapq.heappop(heap)
        heapq.heappush(heap, (f1 + f2, next(tick), (left, right)))
    codes = {}
    def walk(node, prefix):
        if isinstance(node, tuple):
            walk(node[0], prefix + "0")
            walk(node[1], prefix + "1")
        else:
            codes[node] = prefix
    walk(heap[0][2], "")
    return codes

freq = {"a": 7, "b": 4, "c": 3, "d": 2}
codes = huffman_codes(freq)
print(sorted(codes.items()))       # [('a', '0'), ('b', '10'), ('c', '111'), ('d', '110')]
print(sum(freq[s] * len(codes[s]) for s in freq))                     # 30

Thirty bits instead of thirty-two. Decoding walks the bits and emits a symbol as soon as the buffer matches a codeword; because the code is prefix-free, the first match is always the right one:

def encode(text, codes):
    return "".join(codes[ch] for ch in text)

def decode(bits, codes):
    lookup, out, cur = {v: k for k, v in codes.items()}, [], ""
    for b in bits:
        cur += b
        if cur in lookup:                      # prefix-free: first hit is right
            out.append(lookup[cur])
            cur = ""
    return "".join(out)

text = "abacabad"
text_codes = huffman_codes(Counter(text))
bits = encode(text, text_codes)
print(len(bits), decode(bits, text_codes) == text)                    # 14 True

The greedy result against a brute force that tries every pair at every step, which covers every possible code tree, on 300 random frequency tables of up to six symbols. Each code is also checked for being prefix-free and for decoding a random message back exactly:

import random

def best_cost(weights):
    """Brute force: try every pair at every step (every full binary tree)."""
    if len(weights) == 1:
        return 0
    best = None
    for i in range(len(weights)):
        for j in range(i + 1, len(weights)):
            rest = [w for k, w in enumerate(weights) if k not in (i, j)]
            merged = weights[i] + weights[j]
            cost = merged + best_cost(rest + [merged])
            best = cost if best is None else min(best, cost)
    return best

def prefix_free(codes):
    cs = list(codes.values())
    return not any(a != b and b.startswith(a) for a in cs for b in cs)

random.seed(11)
ok = True
for _ in range(300):
    n = random.randint(2, 6)
    freq = {chr(97 + i): random.randint(1, 20) for i in range(n)}
    codes = huffman_codes(freq)
    cost = sum(freq[s] * len(codes[s]) for s in freq)
    ok &= prefix_free(codes) and cost == best_cost(list(freq.values()))
    msg = "".join(random.choices(list(freq), k=30))
    ok &= decode(encode(msg, codes), codes) == msg
print(ok)                                                             # True

The complexity

• Building the code for k distinct symbols takes k - 1 merges, each with two pops and one push on a heap of at most k items: O(k log k).
• Counting frequencies first is O(n) for a text of length n, and encoding is O(n) table lookups.
• Space is O(k) for the heap and the tree.
• If the counts arrive already sorted, a two-queue method builds the same tree in O(k), since merged counts come out in non-decreasing order.

Where it goes wrong

• A single distinct symbol. The tree is one leaf at depth zero, so the natural code is the empty string, and nothing can be decoded. Give it one bit, as the code does.
• Ties. Different tie-breaking produces different codes. The total length is the same, but the decoder must use the same tree as the encoder, which is why compressed formats store the code or a canonical description of it.
• Comparing payloads in the heap. Without the counter, a tie between a symbol and a subtree makes heapq compare a string with a tuple, which raises TypeError.
• Expecting miracles on skewed data. Every codeword is a whole number of bits, so a symbol that makes up 99% of the input still costs a full bit each time. Huffman is optimal among such codes, not among all compression methods; arithmetic coding can get closer to the entropy on skewed inputs.

How to say it in an interview

"I want frequent symbols near the root and rare ones deep. I put the counts in a min-heap, repeatedly pop the two smallest, merge them under a parent with their summed count, and push it back until one node is left. Each merge adds one bit to every occurrence below it, so the encoded size is the sum of the merged counts. It's safe by an exchange argument: some optimal tree has the two rarest symbols as deepest siblings. Building it is O(k log k) for k symbols."

The same "cheapest two first" heap loop solves the minimum cost to connect ropes, and greedy correctness in general is the subject of what makes greedy work. Huffman codes are part of DEFLATE, the format specified in RFC 1951, used by gzip and ZIP.