Huffman Coding

Huffman Coding is the classic greedy algorithm behind file compression (ZIP, JPEG, MP3 all use a variant). The idea is beautiful: give the most frequent symbols the shortest codes, and let a min-heap drive the whole thing.

The slow way first

You could try every possible binary tree shape and measure the total encoded length of each, then keep the best. The number of shapes explodes combinatorially, so brute force is hopeless for more than a handful of symbols.

The question to ask: which two symbols should sit deepest in the tree? The two least frequent ones — they are used rarely, so paying for long codes on them barely costs anything. That single greedy observation is the whole algorithm.

The idea: always merge the two smallest

Put every symbol into a min-heap keyed by frequency. Then repeat: pop the two smallest weights, merge them under a new parent whose weight is their sum, and push that parent back. Each merge places those two nodes one level deeper. When only one node remains on the heap, it is the root of the finished tree.

Because we always merge the two lightest available nodes, rare symbols sink deepest (long codes) and frequent symbols stay near the root (short codes). To read the codes, walk from the root: a left edge appends 0, a right edge appends 1.

Walk through it

Step through the animation. The heap starts as [1(c), 1(d), 2(b), 5(a)]. We pop c and d, merge them into a weight-2 node, and push it back. Now b (2) and that merged node (2) are smallest — merge into weight 4. Finally bcd (4) and a (5) merge into the weight-9 root. Read the paths and you get a=0, b=10, c=110, d=111.

Pseudocode

build a min-heap of (weight, node) for every symbol
while the heap has more than one node:
    pop the two smallest nodes  n1, n2
    parent = a new node with weight = n1.weight + n2.weight
    parent's children are n1 (left) and n2 (right)
    push parent back onto the heap
the one remaining node is the root
read each leaf's code as the path from the root (left=0, right=1)

The Python solution

def huffman(freq):
    heap = [(w, sym) for sym, w in freq.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        w1, n1 = heapq.heappop(heap)
        w2, n2 = heapq.heappop(heap)
        parent = Node(w1 + w2, n1, n2)
        heapq.heappush(heap, (w1 + w2, parent))
    root = heap[0][1]
    return assign_codes(root, "")

• We seed the heap with one entry per symbol, keyed by weight, then heapify to make it a real min-heap in O(n).
• The while loop runs until a single tree remains — each iteration removes two nodes and adds one, so it runs n − 1 times.
• The two heappop calls always return the two smallest weights — that is the greedy choice.
• parent ties them together; pushing it back lets a later merge pull this whole subtree deeper.
• assign_codes does a final walk from the root, appending 0 going left and 1 going right, so each leaf ends up with its path string.

Complexity

The heap is what makes the greedy choice fast: finding the two smallest each round costs O(log n) instead of O(n). With n symbols the whole build is O(n log n).

When this pattern shows up

Practice