Huffman Coding: Optimal Prefix Codes with a Min-Heap

1. Introduction & Motivation

Suppose you must transmit or store a long message drawn from a small alphabet of symbols, and you know each symbol's frequency in advance. A fixed-width code — every symbol gets the same number of bits — is simple but wasteful: a symbol that appears constantly and a symbol that almost never appears pay the exact same price per occurrence. Huffman coding asks a sharper question: given a set of symbols with known (or estimated) frequencies, can we build a variable-length binary code that minimizes the expected number of bits per symbol, while still being unambiguous to decode?

"Unambiguous" is the hard constraint. If codewords can be prefixes of one another — say 0 is one symbol's code and 01 is another's — a decoder reading a bitstream left to right cannot tell, upon seeing 0, whether to stop or keep reading. Huffman coding solves both problems at once: it produces a prefix-free code (no codeword is a prefix of another, so decoding needs no separators or lookahead) that is also optimal — no other prefix-free code achieves a lower expected length for the same frequency distribution.

The elegance of the algorithm is that both properties fall out of the same construction: build a binary tree bottom-up by repeatedly combining the two least-frequent items, and read codewords off as root-to-leaf paths. A tree structure automatically makes the code prefix-free (no leaf is an ancestor of another), and building it by always merging the two smallest frequencies is exactly what makes it optimal — a claim this lesson proves rather than asserts.

2. Prerequisites

This lesson assumes comfort with binary trees, basic probability-free frequency counting, and Big-O notation. It leans heavily on one specific operation: repeated extract-min and insert on a binary min-heap, since Huffman's construction is nothing more than a loop of exactly those two operations. If extract-min, insert, and the heap-order property are not already second nature, work through them first in Heaps, Sorting & Hashing's Heap Operations section — this lesson does not re-derive array-backed heap mechanics from scratch. Advanced Heaps: Leftist, Skew, Pairing, Binomial & Fibonacci is also relevant background: it builds on the same extract-min/insert contract to reach heaps that merge efficiently, and its own prerequisites section points to the same base heap-operations lesson if a refresher is needed.

3. Terminology

• Prefix-free code: a code where no codeword is a prefix of any other codeword. Also called a prefix code (slightly misleading, since the defining property is the absence of prefixing).
• Huffman tree: a full binary tree (every internal node has exactly two children) whose leaves are the alphabet's symbols; the codeword for a symbol is the sequence of 0/1 edge labels from the root to its leaf.
• Weighted path length: for a tree with leaf frequencies $f_i$ at depths $d_i$, the quantity $\sum_i f_i \, d_i$ — exactly the total number of bits needed to encode a stream whose symbol counts match the $f_i$. Minimizing this sum is Huffman's objective.
• Canonical Huffman code: a re-labeling of an optimal code that keeps every codeword's length but reassigns the actual bit patterns by a fixed rule, so that only the length of each symbol's code — not the tree shape — needs to be transmitted to reconstruct a working decoder.

4. A Concrete Example

graph TD
    R(("100")) -->|0| A["a : 45"]
    R -->|1| N4(("55"))
    N4 -->|0| N2(("25"))
    N4 -->|1| N3(("30"))
    N2 -->|0| C["c : 12"]
    N2 -->|1| B["b : 13"]
    N3 -->|0| N1(("14"))
    N3 -->|1| D["d : 16"]
    N1 -->|0| F["f : 5"]
    N1 -->|1| E["e : 9"]
                

Notice the shape this produces: a (frequency 45, by far the largest) sits at depth 1, while f and e (frequencies 5 and 9, the smallest) sit at depth 4. High-frequency symbols end up shallow with short codes; low-frequency symbols end up deep with long codes. That inverse relationship between frequency and depth is precisely what a weighted-path-length minimizer should produce, and it is the visual signature of a correct Huffman tree.

The heap shrinks by one node per merge: it starts with all six leaves, loses one node per merge (two popped, one pushed back), and after the third merge only three nodes remain — the two internal nodes carrying the combined weight of five of the six original symbols, plus a still waiting near the top by virtue of its large individual frequency. Two more merges (not pictured) collapse this down to the single root.

5. Naive Approaches and Their Limits

Fixed-length coding. With $n$ distinct symbols, the obvious code assigns every symbol $\lceil \log_2 n \rceil$ bits. For the six-symbol alphabet above, $\lceil \log_2 6 \rceil = 3$, so every occurrence costs 3 bits regardless of how common the symbol is. Encoding all 100 occurrences costs $100 \times 3 = 300$ bits. This is correct and trivially prefix-free (all codewords share one length), but it ignores the frequency distribution entirely: a symbol that occurs 45 times pays exactly as much per occurrence as one that occurs 5 times. When frequencies are skewed — as real text, DNA, and pixel data usually are — that is a lot of wasted bits.

Greedy-by-frequency without a tree. A tempting shortcut: sort symbols by frequency and hand out shorter codewords to more frequent symbols directly, without building a merge tree. This fails the prefix-free requirement in general. Simply assigning "short codes to frequent symbols" gives no systematic way to guarantee that a short codeword never prefixes a longer one; you would need to solve exactly the same combinatorial structure that the tree already encodes for free. The tree isn't incidental machinery — it is the mechanism that keeps every codeword's set of prefixes reserved for it alone, because two codewords sharing a path from the root diverge at some internal node and become siblings in different subtrees only at their point of divergence.

6. Core Insight

Plain-English steps: (1) create one leaf node per symbol and push all of them onto a min-heap keyed by frequency; (2) while more than one node remains, pop the two smallest, create a new internal node whose frequency is their sum and whose two children are the popped nodes, and push it back; (3) when one node remains, it is the root of the Huffman tree; (4) derive each symbol's code by walking root-to-leaf, appending 0 for a left edge and 1 for a right edge.

7. Correctness Reasoning

The proof that Huffman's greedy merge is optimal follows the same exchange-argument shape used for the greedy-choice proofs elsewhere in this curriculum (see the activity-selection exchange argument in Greedy Algorithms & Exchange-Argument Proofs for the general style) — but the structure being exchanged here is different: instead of swapping which interval is chosen, we swap which symbols occupy the deepest leaves of an optimal tree.

Setup. Fix an alphabet $C$ with frequencies $f(x)$ for each $x \in C$, and let $T^*$ be any optimal full binary tree (every prefix-free code corresponds to a full binary tree; a tree with a single-child internal node can always be shortened without increasing cost, so an optimal tree is full). Let $x, y$ be the two symbols of globally smallest frequency in $C$.

Lemma 1 (exchange step). There exists an optimal tree in which $x$ and $y$ are siblings at the maximum depth. Let $d_{\max}$ be the depth of the deepest leaf in $T^*$, occupied by some symbol $p$. Because $f(x)$ is the globally minimum frequency, $f(x) \le f(p)$. Swapping the positions of $x$ and $p$ changes the total weighted path length by exactly $(f(x)-f(p))\big(\text{depth}(p) - \text{depth}(x)\big)$. Since $f(x)-f(p)\le 0$ and $\text{depth}(p)-\text{depth}(x) = d_{\max}-\text{depth}(x) \ge 0$, this swap cannot increase the cost — so some optimal tree already has $x$ at depth $d_{\max}$. Repeat the identical argument for $y$ against whichever symbol currently occupies $x$'s sibling position at depth $d_{\max}$: since $f(y)$ is the second-smallest frequency overall, the same inequality holds, and the swap again cannot increase cost. After both exchanges, $x$ and $y$ are siblings at the maximum depth in some optimal tree $T$, and $\text{cost}(T) \le \text{cost}(T^*)$, so $T$ is also optimal.

Lemma 2 (merge preserves optimality). Let $T$ be the optimal tree from Lemma 1, with $x, y$ siblings under a parent $z$. Form a reduced alphabet $C' = (C \setminus \{x,y\}) \cup \{z\}$ with $f(z) = f(x)+f(y)$, and let $T'$ be $T$ with the $x$/$y$ pair collapsed into the single leaf $z$. Every other leaf keeps its depth, and $\text{depth}_T(x) = \text{depth}_T(y) = \text{depth}_{T'}(z) + 1$, so:

$$\text{cost}(T) = \text{cost}(T') + f(x) + f(y)$$

This equation is the crux: the collapse-to-$z$ map is a cost-preserving bijection (up to the constant $f(x)+f(y)$) between full binary trees on $C$ that keep $x,y$ as siblings and full binary trees on $C'$. If some tree $U'$ on $C'$ had lower cost than $T'$, expanding $z$ back into the $x,y$ pair would produce a tree $U$ on $C$ with $\text{cost}(U) = \text{cost}(U') + f(x)+f(y) \lt \text{cost}(T') + f(x)+f(y) = \text{cost}(T)$, contradicting the optimality of $T$ from Lemma 1. So $T'$ must be optimal for $C'$.

Putting it together. Lemma 2 says: an optimal tree for $n$ symbols can always be obtained by (a) merging the two globally smallest frequencies into one item, (b) solving the same problem optimally on the remaining $n-1$ items, and (c) expanding the merged item back into its two children. That is exactly Huffman's algorithm, applied recursively. By induction on $|C|$ (base case $|C|=1$: a single leaf at depth 0 is trivially optimal), always merging the two smallest available frequencies — which a min-heap of extract-min/insert operations does directly — builds an optimal prefix code.

8. Complexity Analysis

9. Implementation

Build the tree with a min-heap, derive the code table with one traversal, then encode and decode a sample string to confirm the round trip. All three languages break heap ties with an explicit insertion counter, since comparing tree nodes directly (rather than by frequency) is undefined behavior once two frequencies tie.

import heapq
from itertools import count


class Node:
    __slots__ = ("freq", "char", "left", "right")

    def __init__(self, freq, char=None, left=None, right=None):
        self.freq = freq
        self.char = char        # set only on leaf nodes
        self.left = left
        self.right = right

    def is_leaf(self):
        return self.left is None and self.right is None


def build_huffman_tree(frequencies):
    """
    frequencies: dict mapping symbol -> positive frequency.
    Returns the root Node of the Huffman tree.
    Time: O(n log n) for n distinct symbols (n-1 extract-min pairs + inserts).
    """
    if not frequencies:
        raise ValueError("frequencies must contain at least one symbol")

    tie_breaker = count()  # avoids ever comparing Node objects directly
    heap = [(freq, next(tie_breaker), Node(freq, char=ch))
            for ch, freq in frequencies.items()]
    heapq.heapify(heap)  # O(n)

    while len(heap) > 1:
        freq_a, _, a = heapq.heappop(heap)
        freq_b, _, b = heapq.heappop(heap)
        merged = Node(freq_a + freq_b, left=a, right=b)
        heapq.heappush(heap, (merged.freq, next(tie_breaker), merged))

    return heap[0][2]  # single remaining node is the root (or the lone leaf)


def build_code_table(root):
    """One O(n) traversal deriving symbol -> bitstring codewords."""
    codes = {}

    def walk(node, prefix):
        if node.is_leaf():
            codes[node.char] = prefix or "0"  # single-symbol alphabet needs an explicit 1-bit code
            return
        walk(node.left, prefix + "0")
        walk(node.right, prefix + "1")

    walk(root, "")
    return codes


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


def decode(bitstring, root):
    if root.is_leaf():
        # Degenerate single-symbol tree: every bit represents one occurrence.
        return root.char * len(bitstring)
    decoded = []
    node = root
    for bit in bitstring:
        node = node.left if bit == "0" else node.right
        if node.is_leaf():
            decoded.append(node.char)
            node = root
    return "".join(decoded)


if __name__ == "__main__":
    frequencies = {"a": 45, "b": 13, "c": 12, "d": 16, "e": 9, "f": 5}
    root = build_huffman_tree(frequencies)
    codes = build_code_table(root)
    print("Codes:", codes)
    # Expected: {'a': '0', 'c': '100', 'b': '101', 'f': '1100', 'e': '1101', 'd': '111'}

    sample = "face"
    encoded = encode(sample, codes)
    decoded = decode(encoded, root)
    print("Encoded:", encoded)   # 110001001101
    print("Decoded:", decoded)   # face
    assert decoded == sample

#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <stdexcept>
#include <string>
#include <vector>

struct Node {
    long long freq;
    char ch;          // valid only when leaf == true
    bool leaf;
    std::shared_ptr<Node> left, right;

    Node(long long f, char c) : freq(f), ch(c), leaf(true), left(nullptr), right(nullptr) {}
    Node(long long f, std::shared_ptr<Node> l, std::shared_ptr<Node> r)
        : freq(f), ch('\0'), leaf(false), left(l), right(r) {}
};
using NodePtr = std::shared_ptr<Node>;

// (freq, insertion order) breaks ties deterministically without comparing Node contents.
struct HeapEntry { long long freq; long long order; NodePtr node; };
struct Compare {
    bool operator()(const HeapEntry& a, const HeapEntry& b) const {
        if (a.freq != b.freq) return a.freq > b.freq;  // min-heap on freq
        return a.order > b.order;
    }
};

NodePtr buildHuffmanTree(const std::map<char, long long>& frequencies) {
    if (frequencies.empty()) {
        throw std::invalid_argument("frequencies must contain at least one symbol");
    }
    std::priority_queue<HeapEntry, std::vector<HeapEntry>, Compare> heap;
    long long order = 0;
    for (const auto& kv : frequencies) {
        heap.push({kv.second, order++, std::make_shared<Node>(kv.second, kv.first)});
    }

    while (heap.size() > 1) {
        HeapEntry a = heap.top(); heap.pop();
        HeapEntry b = heap.top(); heap.pop();
        auto merged = std::make_shared<Node>(a.freq + b.freq, a.node, b.node);
        heap.push({merged->freq, order++, merged});
    }
    return heap.top().node;
}

void walk(const NodePtr& node, const std::string& prefix, std::map<char, std::string>& codes) {
    if (node->leaf) {
        codes[node->ch] = prefix.empty() ? "0" : prefix;
        return;
    }
    walk(node->left, prefix + "0", codes);
    walk(node->right, prefix + "1", codes);
}

std::map<char, std::string> buildCodeTable(const NodePtr& root) {
    std::map<char, std::string> codes;
    walk(root, "", codes);
    return codes;
}

std::string encode(const std::string& text, const std::map<char, std::string>& codes) {
    std::string out;
    for (char ch : text) out += codes.at(ch);
    return out;
}

std::string decode(const std::string& bits, const NodePtr& root) {
    if (root->leaf) {
        return std::string(bits.size(), root->ch);
    }
    std::string out;
    NodePtr node = root;
    for (char bit : bits) {
        node = (bit == '0') ? node->left : node->right;
        if (node->leaf) {
            out += node->ch;
            node = root;
        }
    }
    return out;
}

int main() {
    std::map<char, long long> frequencies{{'a',45},{'b',13},{'c',12},{'d',16},{'e',9},{'f',5}};
    NodePtr root = buildHuffmanTree(frequencies);
    auto codes = buildCodeTable(root);

    std::string sample = "face";
    std::string encoded = encode(sample, codes);
    std::string decoded = decode(encoded, root);

    std::cout << "Encoded: " << encoded << "\n";  // 110001001101
    std::cout << "Decoded: " << decoded << "\n";  // face
    return decoded == sample ? 0 : 1;
}

import java.util.*;

public class HuffmanCoding {

    static class Node implements Comparable<Node> {
        final long freq;
        final char ch;         // valid only when leaf == true
        final boolean leaf;
        final Node left, right;
        final long order;      // breaks freq ties deterministically

        Node(long freq, char ch, long order) {
            this.freq = freq; this.ch = ch; this.leaf = true;
            this.left = null; this.right = null; this.order = order;
        }

        Node(long freq, Node left, Node right, long order) {
            this.freq = freq; this.ch = '\0'; this.leaf = false;
            this.left = left; this.right = right; this.order = order;
        }

        @Override
        public int compareTo(Node other) {
            if (freq != other.freq) return Long.compare(freq, other.freq);
            return Long.compare(order, other.order);
        }
    }

    static Node buildHuffmanTree(Map<Character, Long> frequencies) {
        if (frequencies.isEmpty()) {
            throw new IllegalArgumentException("frequencies must contain at least one symbol");
        }
        PriorityQueue<Node> heap = new PriorityQueue<>();
        long[] order = {0};
        for (Map.Entry<Character, Long> entry : frequencies.entrySet()) {
            heap.add(new Node(entry.getValue(), entry.getKey(), order[0]++));
        }

        while (heap.size() > 1) {
            Node a = heap.poll();
            Node b = heap.poll();
            heap.add(new Node(a.freq + b.freq, a, b, order[0]++));
        }
        return heap.poll();
    }

    static void walk(Node node, String prefix, Map<Character, String> codes) {
        if (node.leaf) {
            codes.put(node.ch, prefix.isEmpty() ? "0" : prefix);
            return;
        }
        walk(node.left, prefix + "0", codes);
        walk(node.right, prefix + "1", codes);
    }

    static Map<Character, String> buildCodeTable(Node root) {
        Map<Character, String> codes = new HashMap<>();
        walk(root, "", codes);
        return codes;
    }

    static String encode(String text, Map<Character, String> codes) {
        StringBuilder out = new StringBuilder();
        for (char ch : text.toCharArray()) out.append(codes.get(ch));
        return out.toString();
    }

    static String decode(String bits, Node root) {
        if (root.leaf) {
            char[] out = new char[bits.length()];
            Arrays.fill(out, root.ch);
            return new String(out);
        }
        StringBuilder out = new StringBuilder();
        Node node = root;
        for (char bit : bits.toCharArray()) {
            node = (bit == '0') ? node.left : node.right;
            if (node.leaf) {
                out.append(node.ch);
                node = root;
            }
        }
        return out.toString();
    }

    public static void main(String[] args) {
        Map<Character, Long> frequencies = new LinkedHashMap<>();
        frequencies.put('a', 45L);
        frequencies.put('b', 13L);
        frequencies.put('c', 12L);
        frequencies.put('d', 16L);
        frequencies.put('e', 9L);
        frequencies.put('f', 5L);

        Node root = buildHuffmanTree(frequencies);
        Map<Character, String> codes = buildCodeTable(root);

        String sample = "face";
        String encoded = encode(sample, codes);
        String decoded = decode(encoded, root);

        System.out.println("Encoded: " + encoded);  // 110001001101
        System.out.println("Decoded: " + decoded);  // face
        if (!decoded.equals(sample)) {
            throw new AssertionError("round-trip mismatch");
        }
    }
}

Tracing the Python panel by hand: the heap pops (f,5) then (e,9) first (smallest two), merges them into a 14-frequency node; next pops (c,12) then (b,13); then the 14-node against (d,16); then the two remaining internal nodes (25 and 30); then (a,45) against the 55-node for the root — exactly the merge order in the worked-example table. build_code_table then yields a=0, c=100, b=101, f=1100, e=1101, d=111. Encoding "face" concatenates 1100 (f) + 0 (a) + 100 (c) + 1101 (e) = 110001001101 (12 bits). Walking that bitstring back down the tree from the root — right, right, left, left lands on f; left lands on a; right, left, left lands on c; right, right, left, right lands on e — reproduces f, a, c, e, i.e. exactly "face". The round trip matches.

Canonical Huffman Codes

Transmitting a compressed file also requires transmitting enough information for the receiver to decode it — normally the whole tree shape. But the tree shape carries more information than is strictly needed: only the code length of each symbol matters for the total encoded size, and a decoder can rebuild an equally-valid optimal prefix code from lengths alone. That means the sender only needs to transmit, say, "$a$ gets 1 bit, $b$, $c$, $d$ get 3 bits, $e$, $f$ get 4 bits" — a handful of small integers — instead of serializing pointers or a full binary tree. This is why real compressors (DEFLATE, JPEG's Huffman tables) always convert to canonical form before writing anything to disk.

The canonicalization rule: (1) sort symbols by code length, breaking ties alphabetically for determinism; (2) assign the first symbol the all-zero code of its length; (3) for each subsequent symbol, take the previous numeric code, add 1, and left-shift by however many bits the length increased. This keeps the result prefix-free automatically — incrementing never produces a value whose leading bits collide with a previously assigned shorter code, and left-shifting when the length grows reserves the newly available low-order bits.

def canonical_codes(code_lengths):
    """
    code_lengths: dict mapping symbol -> codeword length in bits, e.g.
    {sym: len(code) for sym, code in build_code_table(root).items()}.
    Returns canonical codes with the SAME lengths as the input -- only
    the bit patterns are reassigned, so total encoded size is unchanged.
    """
    symbols = sorted(code_lengths, key=lambda s: (code_lengths[s], s))

    canonical = {}
    code = 0
    prev_length = 0
    for sym in symbols:
        length = code_lengths[sym]
        code <<= (length - prev_length)     # shift left when length increases
        canonical[sym] = format(code, f"0{length}b")
        code += 1
        prev_length = length
    return canonical


if __name__ == "__main__":
    # Lengths taken from the tree built in the previous snippet.
    original_codes = {"a": "0", "c": "100", "b": "101", "f": "1100", "e": "1101", "d": "111"}
    lengths = {sym: len(code) for sym, code in original_codes.items()}

    canon = canonical_codes(lengths)
    print("Canonical codes:", canon)
    # {'a': '0', 'b': '100', 'c': '101', 'd': '110', 'e': '1110', 'f': '1111'}

    # Every length is preserved, so the total encoded size cannot have changed.
    assert all(len(canon[s]) == lengths[s] for s in lengths)

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <vector>

std::string toBinary(long long value, int width) {
    std::string bits(width, '0');
    for (int i = width - 1; i >= 0; --i) {
        bits[i] = char('0' + (value & 1));
        value >>= 1;
    }
    return bits;
}

std::map<char, std::string> canonicalCodes(const std::map<char, int>& codeLengths) {
    std::vector<char> symbols;
    for (const auto& kv : codeLengths) symbols.push_back(kv.first);
    std::sort(symbols.begin(), symbols.end(), [&](char a, char b) {
        if (codeLengths.at(a) != codeLengths.at(b)) return codeLengths.at(a) < codeLengths.at(b);
        return a < b;
    });

    std::map<char, std::string> canonical;
    long long code = 0;
    int prevLength = 0;
    for (char ch : symbols) {
        int length = codeLengths.at(ch);
        code <<= (length - prevLength);
        canonical[ch] = toBinary(code, length);
        code += 1;
        prevLength = length;
    }
    return canonical;
}

int main() {
    // Lengths taken from the tree built in the previous snippet.
    std::map<char, int> lengths{{'a',1},{'b',3},{'c',3},{'d',3},{'e',4},{'f',4}};
    auto canon = canonicalCodes(lengths);
    for (const auto& kv : canon) {
        std::cout << kv.first << ": " << kv.second << "\n";
    }
    // a: 0  b: 100  c: 101  d: 110  e: 1110  f: 1111
    return 0;
}

import java.util.*;

public class CanonicalHuffman {

    static String toBinary(long value, int width) {
        StringBuilder bits = new StringBuilder();
        for (int i = width - 1; i >= 0; i--) {
            bits.append((value >> i) & 1);
        }
        return bits.toString();
    }

    static Map<Character, String> canonicalCodes(Map<Character, Integer> codeLengths) {
        List<Character> symbols = new ArrayList<>(codeLengths.keySet());
        symbols.sort((a, b) -> {
            int byLength = Integer.compare(codeLengths.get(a), codeLengths.get(b));
            return byLength != 0 ? byLength : Character.compare(a, b);
        });

        Map<Character, String> canonical = new LinkedHashMap<>();
        long code = 0;
        int prevLength = 0;
        for (char ch : symbols) {
            int length = codeLengths.get(ch);
            code <<= (length - prevLength);
            canonical.put(ch, toBinary(code, length));
            code += 1;
            prevLength = length;
        }
        return canonical;
    }

    public static void main(String[] args) {
        // Lengths taken from the tree built in the previous snippet.
        Map<Character, Integer> lengths = new LinkedHashMap<>();
        lengths.put('a', 1);
        lengths.put('b', 3);
        lengths.put('c', 3);
        lengths.put('d', 3);
        lengths.put('e', 4);
        lengths.put('f', 4);

        Map<Character, String> canon = canonicalCodes(lengths);
        for (Map.Entry<Character, String> entry : canon.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
        // a: 0  b: 100  c: 101  d: 110  e: 1110  f: 1111
    }
}

Tracing the Python panel: sorted order is a(1), b(3), c(3), d(3), e(4), f(4). Starting code=0: a gets 0 (1 bit), then code becomes 1; shifting left by $3-1=2$ for b gives $1{\ll}2=4=$100, then code becomes 5 for c=101, then 6 for d=110; shifting left by $4-3=1$ for e gives $7{\ll}1=14=$1110, then 15 for f=1111. These are different bit patterns than the original tree's codes, but the same lengths — so a decoder that only received the lengths $\{a{:}1, b{:}3, c{:}3, d{:}3, e{:}4, f{:}4\}$ can reconstruct this exact canonical table and decode correctly, without ever seeing the original tree.

10. Testing & Edge Cases

11. Applications & Alternatives

Alternative: arithmetic (and range) coding. Huffman coding's one structural limitation is that every codeword must be an integer number of bits, even when a symbol's true information content is fractional (a symbol with probability 0.9 "deserves" about 0.15 bits, but Huffman cannot assign less than 1). Arithmetic coding represents the entire message as a single fraction within $[0,1)$ and can approach the theoretical entropy bound arbitrarily closely, at the cost of a more complex, sequential encode/decode process. Modern codecs (H.265, some JPEG variants) use arithmetic or range coding specifically to close this integer-bit-length gap; Huffman remains preferred where simplicity, speed, and a fixed per-symbol lookup table matter more than the last fraction of a bit.

12. Exercises

Easy

1. Build the Huffman tree and code table for the frequency table $\{p{:}2, q{:}3, r{:}5, s{:}7\}$. Verify the resulting code is prefix-free and compute its total encoded length for one occurrence of each symbol.

Medium

1. Take the code lengths you derived above and produce their canonical Huffman codes by hand, then verify with the canonical_codes implementation that your by-hand result matches.

Hard

1. Design (conceptually, no need to implement) an adaptive Huffman coding scheme: frequencies are not known in advance and must be updated as symbols stream in, with the tree restructured incrementally rather than rebuilt from scratch after every symbol. What invariant would let you detect, in $O(1)$ amortized work per symbol, whether the current tree still satisfies the "sibling property" (nodes listed in non-increasing frequency order have equal-or-adjacent frequencies at each level) that guarantees optimality?

Review rhythm: tomorrow, reconstruct the exchange-argument proof from memory without notes; next week, implement the tree-build, code-table, encode, and decode functions in a language you have not used here; several weeks later, derive canonical Huffman from lengths alone without looking back at this article. Finally, teach the prefix-free requirement and why the greedy merge produces it to someone who already understands binary trees and Big-O.

13. Summary Cheat Sheet

• Huffman coding builds a prefix-free binary code that minimizes expected encoded length for known symbol frequencies.
• Construction: repeatedly extract the two lowest-frequency nodes from a min-heap, merge into a new internal node (sum frequency), reinsert — until one node (the root) remains.
• Codewords are root-to-leaf paths (0 = left, 1 = right); tree structure guarantees prefix-freedom automatically.
• Optimality proof: an exchange argument shows the two globally smallest frequencies can always be made siblings at maximum depth without increasing cost, and merging them reduces to an equivalent, smaller optimal subproblem.
• Time complexity: $O(n \log n)$ for $n$ distinct symbols ($n-1$ merges, each $O(\log n)$ heap work); encode/decode are linear in the input.
• Special-case the single-unique-symbol alphabet: it needs an explicit 1-bit code, since a lone leaf has no root-to-leaf edges to read.
• Canonical Huffman transmits only code lengths, not the tree, by reassigning bit patterns via a fixed sort-and-increment rule — same lengths, same total cost, far less overhead.
• Arithmetic/range coding removes Huffman's integer-bits-per-symbol limitation at the cost of implementation complexity; Huffman remains the default when a simple, fast, table-driven codec is preferred.