The Huffman Algorithm and Its Greedy Proof

From Frequencies to a Binary Tree

When symbols occur with different frequencies, a useful code assigns shorter bit strings to more frequent symbols and longer strings to less frequent ones. The goal is not merely to make each symbol recognizable: among binary prefix codes, we want to minimize the average number of bits per symbol. Huffman’s algorithm solves this optimization problem by building a tree from the symbol weights, merging the two smallest weights at each step.

Let the symbols be a finite nonempty set, and let each symbol \(i\) have a positive weight \(w_i\), such as its frequency in a message. A binary code assigns a finite string of bits to each symbol. It is prefix-free if no codeword is a prefix of another. In the tree representation, each edge is labelled \(0\) or \(1\), and a symbol is placed at a leaf; its codeword is the sequence of labels on the path from the root to that leaf. The depth \(d_i\) of that leaf is the codeword length.

For a code with at least two symbols, we may seek an optimal code among full binary trees. If a code tree has an internal vertex with just one child, bypass that vertex and attach its child directly to its parent (or make the child the root if the vertex was the root). This preserves the code property and shortens the paths to all leaves below that vertex, without increasing \(L\). Repeating this operation removes every such vertex. There are finitely many full binary tree shapes with a fixed finite number of leaves, so an optimal full tree exists. The one-symbol case is separate: its optimal codeword can be the empty string, with length and weighted path length both zero. That empty codeword does not allow a receiver to determine how many copies were sent unless the number of symbols is known in advance.

The Huffman Algorithm

Each merge combines two current items, which may be original symbols or previously formed subtrees. The new weight is the sum of the two weights. To read off a code, label the two child edges at each merge \(0\) and \(1\), in either order. Different edge-label choices give different codewords but do not change their lengths or weighted path length.

Why the Greedy Choice Can Be Optimal

The proof has two parts. First, some optimal tree has the two least-weight symbols as sibling leaves. Second, replacing those sibling leaves by a single leaf of their combined weight reduces the problem to a smaller instance. The cost change under this contraction is exactly the sum of the two weights.

Proof. Choose a leaf \(a\) of maximum depth \(D\). Its sibling cannot be an internal vertex: an internal sibling has a descendant leaf at depth greater than \(D\), contradicting the choice of \(a\). Thus the sibling \(b\) is also a leaf, at depth \(D\). This proves the first claim.

Now take an optimal full tree and such a deepest sibling pair \(a,b\). Let \(x,y\) be symbols of least and second-least weight, so \(w_x\leq w_y\leq w_i\) for every other symbol \(i\). If a symbol of weight \(p\) at depth \(d\) is exchanged with one of weight \(q\) at depth \(D\), the change in weighted path length is \((p-q)(D-d)\). In particular, placing \(x\) at the position of a symbol \(q\) cannot increase the cost: \(w_x\leq q\) and \(D\geq d\). Place \(x\) at one of \(a,b\) this way. Then place \(y\) at the other position if it is not already there. The symbol displaced in this second exchange is neither \(x\) nor \(y\), so its weight is at least \(w_y\); the exchange again cannot increase the cost. The resulting tree still has optimal cost and has \(x,y\) as sibling leaves. \(\square\)

Proof. We use induction on the number \(n\) of symbols. If \(n=1\), the empty codeword has weighted path length \(0\), which is minimum since codeword lengths cannot be negative. Suppose \(n\geq2\) and that the statement holds for every smaller positive number of symbols.

Let \(x,y\) be two symbols of least weight, and set \(s=w_x+w_y\). By the lemma, some optimal full tree has \(x,y\) as sibling leaves. Contract those two leaves and their parent to a single leaf \(z\) of weight \(s\). If the original tree has cost \(L\), the contracted tree has cost \(L-s\): the depths of \(x,y\) were each one more than the depth of \(z\), while all other depths are unchanged. Conversely, expanding a leaf \(z\) of weight \(s\) into sibling leaves \(x,y\) increases the cost by exactly \(s\).

Let the contracted problem consist of \(z\) and all the other symbols. Its minimum cost is \(OPT_c\), and the original minimum cost is \(OPT\). Contracting the optimal tree just described gives \(OPT_c\leq OPT-s\). Conversely, expanding \(z\) in an optimal contracted tree gives a valid original tree, so \(OPT\leq OPT_c+s\). These inequalities imply \(OPT=OPT_c+s\).

Huffman’s algorithm on the original weights first merges \(x,y\), creating precisely the leaf \(z\) of weight \(s\), and then runs Huffman’s algorithm on the contracted weights. This last point matters: the later merges are those of the contracted problem, not a new merge that must combine \(z\) with a particular item. By the induction hypothesis, the tree built from those contracted weights has cost \(OPT_c\). Expanding its \(z\)-leaf into \(x,y\) gives the original Huffman tree and adds exactly \(s\) to the cost. Its cost is therefore \(OPT_c+s=OPT\), as required. \(\square\)

Cost from Merges, and Further Checks

There is a convenient way to calculate the cost without first listing all codewords. Each time two subtrees of weights \(p\) and \(q\) are merged, every original symbol in them gains one unit of depth. The total increase in weighted path length is therefore \(p+q\). Starting with all symbols at depth zero, the final weighted path length is the sum of the weights created at the merges, including the final root weight. This also follows by tracking the contribution of each symbol: its weight is counted once for every merge on its path to the root, which is exactly its final depth.

Common Pitfall and Use

Do not omit the final merge. In the six-symbol example, summing only the first four new weights gives \(14+25+30+55=124\), not the code’s weighted path length. The final merge creates the root of weight \(100\), and it also increases the depth of every symbol by one. Including it gives \(14+25+30+55+100=224\), exactly the weighted path length computed from the codewords. Another common error is to merge a convenient pair rather than the two least current weights: the algorithm’s choice is based on the current items, including subtrees formed at earlier steps.

Huffman coding is useful because it turns a global optimization problem—choosing all codeword lengths at once—into a sequence of local merges with a proof that each initial greedy choice is safe. The sibling-leaf argument identifies an optimal tree compatible with the first merge; contraction then transfers the remaining optimization to a smaller instance. The proof relies on positive weights and a finite symbol set, and it permits arbitrary tie-breaking among equal least weights.