Huffman CodingHuffman coding

01Why it exists

Reach for it when you see:Compression, variable-length codes, shorter codes for more frequent symbols, prefix codes, merging the two smallest each round, building a tree with a min-heap.

02The core idea

Huffman coding answers this question: given how often each character occurs, design a prefix code (no code is a prefix of another) that minimises the sum of frequency × code length. Every prefix code corresponds to a binary tree with the characters at the leaves; the path from the root to a leaf (left 0, right 1) is the code, and the code's length is the leaf's depth. So the problem becomes: how do you arrange the leaves to minimise the weighted sum of depths?

The greedy approach: put every character into a min-heap as its own node, repeatedly pop the two lowest frequencies and push back a new node whose frequency is their sum, until one node is left. The lower a node's frequency, the earlier it gets merged, the deeper it is pushed down the tree, and the longer its code; the most frequent character is usually merged last and ends up shallowest. With n distinct characters there are n − 1 merges, each heap operation costs O(log n), so the total is O(n log n).

Why is it optimal? The exchange argument comes in two parts. First, the two lowest-frequency characters x and y can always sit as siblings on the deepest level: if the deepest siblings in an optimal tree are some other characters a and b, swapping a and b with x and y moves the lower frequencies into the deeper positions, so the weighted total cannot increase. Second, once x and y have been merged into a single node of frequency x + y, what remains is the same problem with one fewer character, and hanging x and y back onto its optimal tree gives an optimal tree for the original. Put together, that is the greedy-choice property plus optimal substructure.

A few things to watch. When frequencies tie, the merge order is not determined, so the Huffman code is not unique either — but the total bit count is the same. With only one distinct character the tree is nothing but a root, so you have to hand it the code 0 as a special case. The decoder needs the same tree, so the file has to carry the code table (DEFLATE uses a set of fixed rules to compress the table itself down to almost nothing). Huffman is optimal among codes that spend a whole number of bits per symbol; allow a fractional number of bits per symbol and arithmetic coding and ANS squeeze harder still, which is the direction taken by xz's LZMA (range coding) and zstd's FSE (a form of ANS).

03The algorithm

1. 1Count how often each character occurs, make one leaf node per character, and put them all in a min-heap ordered by frequency.
2. 2While more than one node remains in the heap: pop the two with the lowest frequencies, a and b.
3. 3Create a new node with frequency a.freq + b.freq, a as its left child and b as its right, and push it back. Repeat until a single node is left; that is the root.
4. 4Walk the whole tree from the root, left is 0 and right is 1, and record a character's code when you reach its leaf.
5. 5To encode, look each character up and concatenate. To decode, start at the root, go left on a 0 and right on a 1, emit a character on reaching a leaf, and return to the root.

04Interactive demo

"abracadabra" has 5 distinct characters. Each step first marks the two lowest frequencies in the heap (yellow), and the next step merges them into a new node (blue) and pushes it back. Once the tree is built, walking down from the root gives the code table, and the totals are compared at the end: 23 bits for Huffman against 33 for a fixed 3-bit code.

05Code

Building the tree with a heap, walking it to produce the code table, plus encoding and decoding. The Python version represents internal nodes as tuples, the C++ version uses pointers.

import heapq
from collections import Counter


def huffman_codes(text):
    """Returns {character: code}. The heap holds (frequency, serial, node); the serial keeps tuples comparable."""
    freq = Counter(text)
    heap = []
    for i, (ch, f) in enumerate(freq.items()):
        heapq.heappush(heap, (f, i, ch))      # a leaf is represented by the character itself
    seq = len(freq)
    while len(heap) > 1:
        f1, _, a = heapq.heappop(heap)        # the two lowest frequencies
        f2, _, b = heapq.heappop(heap)
        heapq.heappush(heap, (f1 + f2, seq, (a, b)))   # an internal node is a (left, right) pair
        seq += 1
    root = heap[0][2]
    codes = {}

    def walk(node, code):
        if isinstance(node, str):             # leaf
            codes[node] = code or "0"         # give "0" when there is only one distinct character
        else:
            walk(node[0], code + "0")
            walk(node[1], code + "1")

    walk(root, "")
    return codes


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


def decode(bits, codes):
    rev = {v: k for k, v in codes.items()}    # prefix code: match as you read, no separators needed
    out, cur = [], ""
    for b in bits:
        cur += b
        if cur in rev:
            out.append(rev[cur])
            cur = ""
    return "".join(out)


if __name__ == "__main__":
    text = "abracadabra"
    codes = huffman_codes(text)
    bits = encode(text, codes)
    print(codes)                              # a takes 1 bit, c and d take 3
    print(len(bits), "bits, fixed length needs", len(text) * 3)   # 23 bits, fixed length needs 33
    print(decode(bits, codes) == text)        # True

06Practice

• LeetCode 1046Last Stone Weight (take the two largest each round)Easy
• LeetCode 1167Minimum Cost to Connect Sticks (premium; identical to Huffman)Medium
• LeetCode 347Top K Frequent Elements (count frequencies, then use a heap)Medium
• LeetCode 767Reorganize String (order by frequency with a heap)Medium
• LeetCode 1000Minimum Cost to Merge Stones (greedy fails once merges must be adjacent; needs interval DP)Hard