Motivation
A binary prefix code assigns a bit string to each symbol so that no codeword is a prefix of another. Frequently used symbols should receive short codewords, but the prefix condition constrains which lengths can coexist. Huffman's algorithm repeatedly combines the two least weights and then reads codewords from the resulting binary tree.
The greedy choice is not justified merely because small weights seem suitable for deep leaves. The proof must show that some globally optimal tree has the two least weights as deepest siblings, and that contracting those siblings leaves an optimal smaller problem.
Definitions
Definition 2.7.1
(Prefix codes and Huffman’s algorithm)
Let there be symbols with nonnegative weights . A binary prefix code assigns distinct finite binary strings such that no codeword is a prefix of another. Its cost is , where is the length of symbol 's codeword. A code corresponds to labeled leaves of a binary tree: left and right edges are labeled zero and one, and a leaf's root-to-leaf labels give its codeword.
For , Huffman's algorithm repeatedly removes two minimum-weight nodes, creates their parent with weight equal to their sum, and reinserts it. Once one node remains, label the two child edges of every internal node zero and one. For , this unit permits the empty codeword and cost zero. If a communication format requires a nonempty word or does not separately know the number of symbols, that is a different convention.
Theorems
Theorem 2.7.2
(Greedy sibling property)
For , some minimum-cost binary prefix-code tree has the two least weights as sibling leaves at maximum depth.
Theorem 2.7.3
(Huffman optimality)
For nonnegative weights, the Huffman construction returns a minimum-cost binary prefix code under the stated convention. An indexed min-heap implementation constructs the code tree in time and space for ; explicitly writing all codewords additionally costs time proportional to their total length.
Proof sketch or proof idea
Proof
(Exchange and contraction)
A code tree can be made full, meaning each internal node has two children, without increasing cost: contract a unary internal node and shorten the codewords below it. Nonnegative weights ensure shortening cannot increase the weighted cost. Among full trees with labeled leaves, a minimum exists because there are finitely many such tree shapes and labelings.
In a full tree, a leaf of maximum depth has a sibling that is also a leaf; otherwise that sibling has a descendant at greater depth. If a lighter weight occupies a shallower leaf than a heavier weight, swapping the two does not increase cost. Indeed, for weights and depths , the cost change after placing at depth and at depth is . Repeated exchanges place the two least weights at a deepest sibling pair in some optimum.
Let those weights be . Contract their sibling leaves into a single leaf of weight . Every other depth is unchanged, while the two original leaves were one level below the contracted leaf. Hence the original cost equals the contracted-tree cost plus . If the contracted tree were not optimal for the smaller weight multiset, replacing it by a cheaper tree and expanding the merged leaf into two children would contradict optimality of the original. Conversely, expanding an optimal smaller tree increases cost by exactly . Induction on proves Huffman's sequence of minimum-weight merges is optimal, including ties and zero weights.
A binary min-heap stores the current weights. Each of the merges performs two extract-min operations and one insertion, each taking time; inserting the initial weights costs at most . The tree has leaves and internal nodes, so storage is . Edge labels can be assigned afterward.
Proof X-ray
Exchange and contraction play different roles
The exchange shows that a greedy pair can appear together in some optimum. Contraction shows that the rest of that optimum solves a smaller instance. Both steps are needed for induction.
Nonnegativity enters only in the first step, where shortening a unary node must not raise the cost. The exchange inequality uses only the order of the weights, and the contraction identity is exact for any weights. Any sibling leaf pair satisfies the contraction identity; the exchange is what guarantees that the two least weights, at deepest siblings, occur together in an optimum.
Worked examples
Worked example 2.7.4
(Four weights)
For weights , merge , then , then . The resulting code lengths can be , giving cost . The merge weights also sum to .
Worked example 2.7.5
(A tie can change the code)
With four equal positive weights, the first two selected symbols may be any pair. Different tie choices and left/right labels give different codewords, but every Huffman result has the same optimal weighted cost.
Worked example 2.7.6
(A zero weight)
For weights , merge and one of the unit weights, then merge the result with the other unit weight. The two positive weights have depths two and one, so the cost is three. The zero-weight symbol is still assigned a distinct prefix-code leaf.
Common mistakes
Counterexample mode
Negative weights remove the minimum
Claim: Huffman's construction is optimal for arbitrary real weights. Take two symbols of weights and . Huffman gives both words length one and cost . But the code with word 0 for the weight- symbol and the word consisting of ones for the weight- symbol is a valid prefix code of cost . As grows this is unbounded below, so no minimum-cost code exists. Nonnegativity is therefore essential: it makes shortening a unary node safe and keeps the cost bounded below.
Common mistake
(Choosing short codewords independently)
The strings 0 and 01 cannot both be codewords in a prefix code, because 0 is a prefix of 01. Assigning the individually shortest available-looking strings without checking the whole tree can produce an invalid code. Read the codewords off the leaves of one binary tree, where no word can be a prefix of another.
Common mistake
(Believing every optimal tree uses the merged pair)
The proof finds an optimal tree containing a suitable greedy sibling pair; it does not say every optimal tree must use exactly the same pair when weights tie.
The single-symbol empty-codeword convention must be stated because some practical formats impose a nonempty codeword.
Prefix codes and trees
A binary codeword describes a path from the root. If one codeword were a prefix of another, its path would end at an ancestor of the other codeword's leaf. A prefix-code tree therefore has all codewords at leaves. Conversely, in any binary tree, paths to distinct leaves cannot be prefixes of one another, so labeling the two child edges with different bits produces a prefix code.
A tree with a unary internal node can be shortened by removing that node and joining its child directly to its parent, or by moving the child to the root if the unary node is the root. All leaf paths in that subtree lose one bit, and prefix-freeness remains intact. With nonnegative weights this does not increase the cost. If all weights below the node are zero, the cost may stay equal; the proof needs only the existence of a full optimum, not that every optimum is full.
A full binary tree with leaves has internal nodes. One proof counts edges: every internal node has two children, giving edges, while a finite tree with nodes has edges. Hence . This finiteness makes it legitimate to choose an optimal full labeled tree even though codeword lengths are not bounded in the definition.
Worked example 2.7.7
(A larger merge sequence)
For weights , Huffman merges , then , then . The weighted cost is . One tree has depths , giving . The two calculations agree.
The exchange argument with ties
Fix an optimal full tree and a deepest sibling pair. If one of the two smallest weights is not already in that pair, swap it with a weight occupying one of those deepest leaves. The smaller weight moves to a depth no smaller than before, and the larger weight moves to its former depth. The algebra in the proof shows that this cannot increase cost. Repeat for the other smallest weight, taking care to keep the first at a deepest sibling leaf.
The resulting tree has cost no greater than an optimum, so it is also optimal. If some weights or depths are equal, a swap may leave the cost unchanged. That is enough: the theorem claims the existence of an optimum with the chosen pair, not that all optima have that pair. This existential form is what lets the greedy algorithm choose any two minimum weights when ties occur.
After contraction, the merged weight represents the total weight below that leaf. Every additional level above it contributes once to both original leaves, hence contributes their sum. Expanding the leaf adds one level to each of the two original symbols and adds exactly to cost. This identity is independent of where the contracted leaf lies in the smaller tree.
Why merge weights sum to the cost
Concept lensStructural
Cost as a sum over internal nodes
Each merge creates one internal node whose weight is the sum of all original leaf weights in its subtree. Sum these internal-node weights over the full Huffman tree. A leaf of weight contributes to precisely one internal-node weight for each ancestor, and the number of ancestors equals its depth . Therefore the sum of merge weights equals .
This identity provides an independent way to compute the cost of a constructed tree. It does not by itself prove optimality: a different merge sequence also has a sum of internal weights. The exchange and contraction proof establishes why choosing two least weights at every step minimizes that sum among valid code trees.
The exact bits assigned to left and right edges do not change codeword lengths or cost. They do affect the actual codebook, so an encoder and decoder must use the same labeled tree or an agreed canonical representation. The mathematical optimization problem here concerns weighted length; transmitting a codebook, framing messages and handling corrupted streams are separate issues.
Output and complexity
The heap analysis constructs a tree with nodes in heap time. If the requested output is an explicit bit string for every leaf, writing those strings takes time proportional to . A full binary tree can have highly unequal depths, so that output length can exceed . Reporting only the heap bound as the time to print every codeword would ignore the size of the output.
The proof assumes exact comparison and addition of the supplied weights. If weights are rational numbers with binary encodings, an implementation must represent sums and compare them correctly; the simple heap-operation count is not by itself a complete bit-complexity analysis for arbitrary representations. Negative weights are excluded: shortening a negative-weight codeword could increase the objective, so the full-tree reduction would not follow from the same argument.
When , the empty word is the unique leaf path and gives cost zero in this mathematical convention. It is prefix-free for a one-symbol alphabet, but a stream of empty codewords does not reveal how many symbols were sent without external framing. If a format requires one bit per symbol, its constrained optimum is different. This is a modeling choice, not an exception hidden in the greedy proof.
Checking a claimed code
To check a proposed code, first confirm that no listed codeword is a prefix of another. Then calculate the weighted length from the given weights and codeword lengths. For a tree produced by Huffman's algorithm, the sum of merge weights is a useful arithmetic cross-check. A valid prefix code with a low cost is not automatically optimal; optimality follows from the greedy sibling and contraction theorem or from a separate lower-bound certificate.
If the weights represent probabilities, they may sum to one, but normalization is unnecessary for the optimization: multiplying every weight by the same positive constant scales every code cost equally and does not change which code is optimal. Zero weights are allowed, and the algorithm still constructs a codeword for each listed symbol. The proof treats weights as nonnegative costs without assuming any stochastic model.
For probabilities, the optimal average length lies within one bit of the entropy.
A natural next question
How close to the entropy can a prefix code get?
For probabilities, the optimal average length lies within one bit of the entropy.
If the weights are probabilities , an optimal binary prefix code has average length with , where . The weights above have probabilities , so and the lower bound is attained. For probabilities we get but , so the gap can be almost one bit.
Summary
A full optimum can place the two least weights at deepest sibling leaves. Contracting that pair reduces the problem and changes the cost by their sum. Repeating the safe merge yields an optimal prefix-code tree.
Exercises
Quick check
(What is the Huffman cost for two symbols of weights and ?)
Solution · Answer
Both codewords have length one, so the cost is .
Quick check
(Why can a deepest leaf's sibling not be an internal node in a full finite tree?)
Solution · Answer
An internal sibling would have a descendant leaf deeper than the chosen maximum-depth leaf.
Quick check
(What weight is assigned to a parent created by merging weights and ?)
Solution · Answer
The parent receives weight .
Quick check
(Why does the proof permit ties?)
Solution · Answer
The exchange and contraction arguments use non-strict inequalities, so any choice among equal minimum weights can be used in some optimum.