Huffman Coding

Intuition

Suppose a text uses a few symbols with very different frequencies. A fixed-length code wastes bits: with 5 symbols, every character costs 3 bits. A variable-length code gives frequent symbols short codewords and rare symbols long ones. To decode without separators, the code must be prefix-free: no codeword is the beginning of another. Then a prefix-free code is exactly a binary tree whose leaves are the symbols; the path from the root (left = 0, right = 1) spells the codeword, and decoding just walks the tree from the root until it reaches a leaf.

The cost of the code is the total number of bits:

cost = sum(freq[s] * depth(s))

which is also called the weighted path length of the tree. Huffman's algorithm builds a tree with the minimum possible cost using a simple greedy rule:

1. Start with one single-node tree per symbol, weighted by its frequency.
2. Remove the two trees with the smallest weights and join them under a new root whose weight is their sum.
3. Repeat until one tree is left.

A min-heap makes each step O(log n).

Why the greedy is optimal (the exchange argument interviewers like to hear):

• In some optimal tree, the two least frequent symbols are siblings at the deepest level. If a deeper leaf had a larger frequency than a shallower one, swapping them would not increase the cost.
• Merge those two symbols into one "super-symbol" with their combined weight. Any tree for the reduced problem becomes a tree for the original by splitting that leaf, and the cost grows by exactly w1 + w2, regardless of shape. So an optimal reduced tree gives an optimal original tree, and induction finishes the proof.

A useful identity falls out: the total cost equals the sum of all merge weights, because each merge pushes every leaf below it one level deeper. That is why "minimum cost to connect ropes" (each connection costs the sum of the two lengths) is the same problem: you never need to build the tree at all.

When to use it in interviews / OAs

• "Combine everything into one; each combination costs the size of the result; any two items may be combined": connecting ropes or sticks, merging files, joining piles. Greedily combine the two smallest with a min-heap.
• Compression questions in CS-fundamentals rounds: explain prefix codes, build a code table for given frequencies, encode and decode.
• Variants with a different combine rule can still be greedy on the two smallest. For example, when splitting a worker costs split time and blocks take t time, repeatedly replacing the two smallest times a <= b with split + b gives the minimum total time.

Watch for the trap: if only adjacent items may be merged (piles in a row), the greedy is wrong and you need interval DP.

Template

Minimum total merge cost, the form you will most often meet in an OA:

import heapq


def min_merge_cost(weights: list[int]) -> int:
    # Merge everything into one; each merge costs the sum of the two parts.
    heap = list(weights)
    heapq.heapify(heap)
    total = 0
    while len(heap) > 1:
        a = heapq.heappop(heap)  # Always merge the two lightest pieces.
        b = heapq.heappop(heap)
        total += a + b
        heapq.heappush(heap, a + b)
    return total


assert min_merge_cost([2, 4, 3]) == 14  # (2+3) + (5+4)
assert min_merge_cost([1, 8, 3, 5]) == 30 and min_merge_cost([5]) == 0

Building actual codes. Internal nodes are tuples (left, right) and leaves are symbols; a counter breaks ties so the heap never compares two subtrees.

import heapq
from itertools import count


def huffman_codes(freq: dict[str, int]) -> dict[str, str]:
    if len(freq) <= 1:  # Empty input, or a single symbol that still needs a 1-bit code.
        return {sym: "0" for sym in freq}
    tick = count()  # Tiebreaker, so the heap never compares two subtrees.
    heap = [(f, next(tick), sym) for sym, f in freq.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        f1, _, left = heapq.heappop(heap)
        f2, _, right = heapq.heappop(heap)
        heapq.heappush(heap, (f1 + f2, next(tick), (left, right)))  # An internal node is a pair.
    codes: dict[str, str] = {}
    stack = [(heap[0][2], "")]
    while stack:
        node, path = stack.pop()
        if isinstance(node, tuple):
            stack.append((node[0], path + "0"))  # Left edge = 0, right edge = 1.
            stack.append((node[1], path + "1"))
        else:
            codes[node] = path
    return codes


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


def decode(bits: str, codes: dict[str, str]) -> str:
    reverse = {c: s for s, c in codes.items()}
    out, cur = [], ""
    for b in bits:
        cur += b
        if cur in reverse:  # Prefix-free: the first match must be a whole symbol.
            out.append(reverse[cur])
            cur = ""
    return "".join(out)


text = "abracadabra"
codes = huffman_codes({ch: text.count(ch) for ch in set(text)})
bits = encode(text, codes)
assert decode(bits, codes) == text and len(bits) == 23  # 23 bits instead of 33 with a fixed 3-bit code.
assert len(codes["a"]) == 1  # The most frequent symbol gets the shortest code.

For long inputs, decode by walking the tree bit by bit instead of growing a string and looking it up in a dict; that keeps decoding linear in the number of bits.

Complexity

• Building with a heap: O(n log n) time for n distinct symbols, O(n) space.
• If the weights are already sorted, a two-queue trick reaches O(n): keep original leaves in one queue and merged trees in another; merged weights come out in non-decreasing order, so the two smallest are always at the queue fronts.
• Encoding is O(total output bits); decoding by walking the tree is O(number of bits).

Common pitfalls

• Comparing trees in the heap. Tuples (weight, subtree) fail on ties when subtrees are not comparable. Add a unique counter as the second field.
• A single distinct symbol. The loop produces a tree with zero depth and an empty code; assign it "0" explicitly. For merge-cost problems, one item costs 0.
• Sorting once instead of using a heap. Merged weights must re-enter the pool; sorting the input once and adding left to right is not the same algorithm.
• Adjacent-only merges. "Merge stones in a row" is interval DP, not Huffman.
• Merging k at a time. For k-ary trees, first pad with zero-weight dummy symbols until (n - 1) % (k - 1) == 0, then always merge the k smallest. Without padding the greedy can be suboptimal.
• Overflow in Java/C++. Totals grow like sum(weights) * log n; use 64-bit integers.

Interview variations

• Minimum cost to connect ropes / sticks: exactly the merge-cost template.
• Optimal merge pattern for sorted files: the cost of merging two files is the sum of their sizes; same greedy.
• Huffman encode/decode: build the table, encode a string, and decode a bit string by walking the tree.
• Minimum time to build blocks with worker splitting: the same "two smallest" greedy with split + max(a, b) as the combine rule.
• k-ary Huffman: merge k items at a time after padding with zero weights.
• Contrast question: why merging adjacent stones needs DP while merging arbitrary piles does not.