6.2 Huffman coding and heap applications

Motivation

A fixed-length code spends the same number of bits on every symbol. That is simple, but it ignores a useful fact about real data: symbols usually occur at very different frequencies. If a occupies almost half a file while f appears only occasionally, making their codewords equally long wastes space. Huffman coding uses a binary tree and a min-priority queue to assign short paths to frequent symbols and longer paths to rare ones.

There are three separate questions to keep straight. First, construction asks how repeated minimum-frequency merges produce a tree. Second, decodability asks why a stream of variable-length codewords can be split without separators. Third, cost asks how many bits the resulting code uses under a stated frequency model. A correct solution must answer all three; a plausible-looking tree alone is not enough.

The same heap pattern appears in a different setting. When merging k sorted lists, the next output is the smallest among the lists' current heads. A min-heap keeps precisely those candidates and avoids rescanning all k heads after every output. Both applications repeatedly maintain a small frontier of currently eligible minimum items.

Definitions

The repeated two-minimum construction

Create one leaf for each symbol and key it by frequency. Put all leaves in a min-heap. Repeatedly remove the two minimum-weight roots, attach them below a new internal node whose weight is their sum, and insert that node back into the heap. With m leaves there are exactly m - 1 merges, because every merge reduces the number of heap items by one.

HUFFMAN(symbols with positive weights)
    H = a min-heap containing one leaf per symbol
    while size(H) > 1
        x = deleteMin(H)
        y = deleteMin(H)
        z = a new internal node with weight x.weight + y.weight
        z.left = x
        z.right = y
        insert(H, z)
    return deleteMin(H)

Choosing x as the left child gives a reproducible convention, but exchanging the left and right children of any internal node remains valid. Such an exchange changes bit strings, not codeword lengths or storage cost. Equal weights can also permit different merge orders. Therefore a Huffman tree need not have a unique printed code table.

At every stage the heap contains roots of disjoint subtrees whose leaves partition the alphabet. A merge preserves that forest invariant: it replaces two disjoint parts by their union and gives the new root the sum of all leaf weights below it. When one root remains, every symbol occurs exactly once as a leaf of one full binary tree.

If the input contains N symbols, counting frequencies costs O(N). A bottom-up heap can be built from the m leaves in O(m) time. The m - 1 rounds each perform two deleteMin operations and one insertion, each bounded by O(log m), so tree construction is O(m log m). Traversing the final tree to record all codes is O(m). Thus the complete preprocessing cost is O(N + m log m); if a frequency table is already supplied, the O(N) scan is absent. Encoding performs one code-table lookup per input symbol plus work proportional to the number of bits emitted; decoding is linear in the number of bits read.

For an alphabet with just one symbol, the merge loop produces a one-node tree and an empty path. Practical formats normally assign that symbol the code 0 so repeated occurrences still have an explicit representation. The six-symbol course example does not need this edge-case convention.

Theorem/Proposition

These propositions establish the properties used below. The construction is the Huffman greedy algorithm, but a full exchange proof that it minimizes weighted length among all binary prefix trees is beyond this unit's source scope. We do not assume such a proof in the numerical or decoding arguments.

Proof Sketch or Proof Idea

For the first proposition, suppose one leaf code were a prefix of another. Following the shorter code from the root would reach its leaf and then would have to continue along more edges to reach the second symbol. A leaf has no children, so this is impossible. The claim depends on symbols being stored at leaves rather than at internal nodes.

For unique decoding, start at the root and consume bits one at a time. The first reached leaf forces the first symbol: stopping earlier would mean an internal node had a code, while continuing would mean a leaf code was a prefix of a longer code. Output that leaf, return to the root, and repeat. Induction on the remaining codewords gives a unique complete decoding. If the stream ends at an internal node, it is truncated or invalid rather than a second valid decoding.

For the merge-sum identity, joining roots of weights p and q increases the depth of every leaf in those two subtrees by one. The weighted-length increase is therefore exactly p + q, the new internal-node weight. Starting from isolated leaves at depth zero and summing this increase across all merges gives the final weighted external path length. This is also a powerful arithmetic cross-check: a code-length calculation and a merge-total calculation should agree.

For heap-based multiway merging, maintain the invariant that the heap contains exactly the first unconsumed item of every nonempty list. Because each list is sorted, every unconsumed item in that list is at least its head. The smallest heap key is therefore the smallest item remaining anywhere. Removing it is safe; inserting the successor from the same list restores the invariant.

Worked Examples

                           (100)
                         0 /   \ 1
                       a:45    (55)
                              0 /  \ 1
                              (25)  (30)
                             0/ \1  0/ \1
                          c:12 b:13 (14) d:16
                                    0/ \1
                                  f:5 e:9

MERGE_K_SORTED_LISTS(lists)
    H = empty min-heap
    for each nonempty list i
        insert(H, (lists[i].head.value, i, lists[i].head))
    output = empty list
    while H is not empty
        (value, i, node) = deleteMin(H)
        successor = node.next
        append value to output
        if successor exists
            insert(H, (successor.value, i, successor))
    return output

Common Mistakes

• Combining the two largest weights, or continuing to use a stale sorted list of original frequencies. Each round must select the two current minima, including internal nodes inserted by earlier rounds.
• Reading codes from leaves upward. Codes are root-to-leaf paths; reversing a path changes the code.
• Placing a source symbol at an internal node. Then its code can prefix a descendant's code, destroying separator-free decoding.
• Claiming that frequent symbols must always have strictly shorter codes. The construction tends to make them shallow, but equal lengths and tie-dependent trees are normal. The exact tree, not frequency rank alone, determines a codeword.
• Comparing only the number of codewords. Storage is the weighted sum of lengths, and the stated 224,000 bits excludes tree/header overhead.
• Saying six symbols need two fixed bits because 2^2 is close to six. Two bits represent only four distinct values; six symbols require three bits.
• Putting every element from all k lists in the merge heap. Only the current head of each nonempty list is eligible, so the heap should have at most k items.

Summary

Huffman construction repeatedly joins the two minimum-weight roots in a min-heap. The resulting symbols are leaves, so root-to-leaf codes are prefix-free and concatenated codewords decode uniquely. For the normalized six-symbol table, the merges are 5+9=14, 12+13=25, 14+16=30, 25+30=55, and 45+55=100; the lengths are 1,3,3,3,4,4, and a 100,000-character payload occupies exactly 224,000 bits. That saves 576,000 bits against the stated 8-bit ASCII comparison and 76,000 bits against the shortest three-bit fixed-length code.

The heap is not specific to compression. For k sorted lists, keeping one current head per nonempty list lets each of n outputs choose the global minimum in O(log k) time, for O(n log k) total time and O(k) auxiliary space.

Exercises

1. Starting from weights 5, 9, 12, 13, 16, 45, show every Huffman merge and the heap's remaining weights after each insertion.
2. Using the code table in the complete construction, decode 11011100111. Show the leaf boundaries rather than guessing equal-length groups.
3. Recompute the six-symbol payload cost by both weighted code lengths and the merge-sum identity. Then state the savings against 8-bit ASCII and a shortest fixed-length code for six symbols.
4. Decide whether the set {0, 01, 11} is prefix-free. Explain the practical decoding consequence.
5. Give heap pseudocode for merging k sorted linked lists. State the heap invariant, time complexity in terms of total length n, and auxiliary space complexity.

Solutions