Huffman Coding and Optimal Merge Patterns

Huffman coding builds an optimal prefix code for a set of symbols with known frequencies: no codeword is a prefix of another, so a bit stream decodes uniquely without separators, and the expected codeword length is minimised among all binary prefix codes.

The construction is a textbook greedy algorithm: repeatedly merge the two lightest trees. The same merge pattern also solves optimal merge patterns (combine $n$ sorted files of given lengths at minimum total cost). Both belong to the greedy part of the syllabus and reuse a binary heap as the priority queue.

A code is prefix-free (a prefix code) when no codeword is a prefix of another. Equivalently, the codewords are the root-to-leaf paths of a binary tree whose leaves are the symbols (left = 0, right = 1, or the reverse). Fixed-length codes are prefix-free but usually longer than necessary when frequencies are skewed.

The cost of a tree $T$ for frequencies $f(c)$ is

where $d_T(c)$ is the depth of leaf $c$ (edge count). $B(T)$ is the total number of bits used to encode a file whose symbol counts are the $f(c)$ values.

An optimal prefix code corresponds to a full binary tree: every internal node has exactly two children. A node with one child can be bypassed, shortening every codeword in that subtree and lowering $B(T)$.

Given $n$ sorted runs of lengths $\ell_1, \ldots, \ell_n$, merging two runs of lengths $a$ and $b$ costs $a + b$. The total cost of a binary merge tree equals the sum, over every internal node, of the combined size of its two children, which is the same formula as $B(T)$ with $f(c) = \ell_c$. So Huffman’s construction also yields an optimal merge order.

Pseudocode uses 1-based arrays, <- for assignment and a min-priority queue Q of trees keyed by freq.

Input. A set $C$ of $n \ge 2$ symbols, each with a positive frequency freq.

Output. The root of an optimal Huffman tree.

Time. With a binary heap, each of the $n - 1$ iterations does two extract-mins and one insert: $O(n \lg n)$. Building the initial heap is $O(n)$. Space $\Theta(n)$ for the tree nodes.

Counting facts. The loop runs exactly $n - 1$ times, so the tree has $n$ leaves, $n - 1$ internal nodes, $2n - 1$ nodes in all and $2n - 2$ edges. The queue sees $2(n-1)$ EXTRACT-MIN calls inside the loop (plus the final one) and $n - 1$ INSERT calls. If the frequencies arrive already sorted, two FIFO queues (one for the original leaves, one for the merged nodes, whose keys come out in nondecreasing order) give an $O(n)$ construction.

Edge cases. $n = 2$: one merge, codewords 0 and 1. Equal frequencies: any tie-breaking among equal keys is allowed; different trees may arise, but all are optimal. Zero frequency is excluded (a zero-frequency symbol can be dropped before coding).

Lemma (CLRS 3e, Section 16.3). Let $x$ and $y$ be two symbols of lowest frequency. There exists an optimal prefix code in which the codewords for $x$ and $y$ have the same length and differ only in the last bit (they are siblings in the tree).

Idea. Order the two minimum frequencies as $f(x)\le f(y)$. Choose deepest sibling leaves $a,b$, ordered so $f(a)\le f(b)$. After resolving coincident symbols by relabelling, $f(x)\le f(a)$ and $f(y)\le f(b)$. Move the lower-frequency symbols to those deeper positions by exchanges. Each exchange changes cost by $(f(x)-f(a))(d(a)-d(x))\le0$, or the analogous expression for $y,b$. Thus an optimal tree exists with $x,y$ deepest siblings.

Replace $x$ and $y$ by a single symbol $z$ of frequency $f(x) + f(y)$. An optimal tree for the reduced alphabet, expanded by making $x$ and $y$ the children of $z$, is optimal for the original alphabet. The cost increases by exactly $f(x) + f(y)$ (one extra bit on every occurrence of $x$ or $y$).

Together, the two properties justify the algorithm: each merge is a safe greedy choice, and the residual problem is again a Huffman instance.

where $f(z)$ is the sum of the frequencies of the leaves in $z$'s subtree (equivalently, the sum of the frequencies of $z$'s two children). This matches the total merge cost in an optimal merge pattern.

Frequencies: $a:45$, $b:13$, $c:12$, $d:16$, $e:9$.

Codewords (left = 0, right = 1; children ordered as extracted):

At the root, $a$ (extracted first in step 4) is the left child and $z_3$ the right; inside $z_3$, $z_1$ is left and $z_2$ right. The exact bit strings depend on this left/right convention; the lengths do not. Weighted external path length:

Check via internal nodes: $21 + 29 + 50 + 95 = 195$.

Lengths 20, 30, 10, 25. Merges:

Total cost $30 + 55 + 85 = 170$. The cost depends only on which runs end up merged together (the shape of the merge tree), not on the order in which independent merges are carried out. Merging the two largest first (30 with 25, then 55 with 20, then 75 with 10) costs $55 + 75 + 85 = 215$, which is worse.

With the code of the five-symbol example ($a = 0$, $e = 100$, $c = 101$, $b = 110$, $d = 111$), decode 1100101111. Walk from the root and restart at the root at each leaf: 110 gives $b$, 0 gives $a$, 101 gives $c$, 111 gives $d$. The message is $bacd$. No separators are needed because no codeword is a prefix of another.

Frequencies $1, 1, 2, 2$ (symbols $p, q, r, s$). The first merge is forced: $p + q = 2$. Now three keys equal 2 (the new node and $r$, $s$).

Both trees are optimal, but the maximum codeword length (2 versus 3) and the set of lengths differ. A question that asks for "the" length of a symbol must fix a tie-breaking rule.

With probabilities $p_c = f(c) / \sum f$, the average length $L = \sum p_c \ell_c$ of an optimal prefix code satisfies $H \le L < H + 1$, where $H = -\sum p_c \lg p_c$ is the entropy (in bits per symbol). For the five-symbol example, $L = 195/95 \approx 2.053$ and $H \approx 2.035$.

Common misconceptions.