---
title: Huffman Codes
module: Greedy Algorithms
moduleNumber: 7
lessonNumber: 3
order: 703
summary: |
  Huffman coding builds a
  provably optimal prefix-free binary code by repeatedly merging the two least
  frequent symbols. We develop prefix-free codes as binary trees, give the
  algorithm with a priority queue, build a Huffman tree from example
  frequencies, prove optimality with the same greedy-choice-plus-substructure
  argument, and pin the running time at $O(n\log n)$.
topics: [Greedy Algorithms]
sources:
  - book: CLRS
    ref: "Ch. 16 — Greedy Algorithms (Huffman Codes)"
  - book: Skiena
    ref: "§5 — Data Compression"
  - book: Erickson
    ref: "Ch. 4 — Greedy Algorithms (Huffman Codes)"
practice:
  - title: 'Last Stone Weight'
    slug: last-stone-weight
    difficulty: Easy
  - title: 'Minimum Cost to Connect Sticks'
    slug: minimum-cost-to-connect-sticks
    difficulty: Medium
  - title: 'Reorganize String'
    slug: reorganize-string
    difficulty: Medium
  - title: 'Minimum Cost to Merge Stones'
    slug: minimum-cost-to-merge-stones
    difficulty: Hard
---

Suppose we want to store or transmit a file of text drawn from some alphabet of
symbols, letters being the obvious case. A **fixed-length code** assigns every
symbol a bit string of the same length: with $6$ symbols we would spend $3$ bits
each ($\lceil \log_2 6 \rceil = 3$), regardless of how often each symbol appears. But
real text is lopsided. In English, `e` and `t` are everywhere while `q` and `z`
are rare. It is wasteful to spend as many bits on `z` as on `e`.

A **variable-length code** exploits this skew: give the frequent symbols _short_
codewords and the rare symbols _long_ ones, so the total bit count drops.
Huffman's 1952 algorithm finds the variable-length code that compresses a given
file as much as any such code possibly can, and it does so with a simple greedy
rule.[^skiena-huffman] This lesson is the payoff of the [greedy
method](/algorithms/greedy/the-greedy-method): a non-obvious algorithm, a short
correctness proof, and a result used billions of times a day inside
JPEG, MP3, gzip, and PNG.

## Prefix-free codes

Variable-length codes carry a hazard. If `e` is `0` and `t` is `01`, then the
stream `001` is ambiguous (is it `e e t`? `e ?`?) because the codeword for `e`
is a _prefix_ of the codeword for `t`. To decode unambiguously without separator
symbols, we insist on a **prefix-free code** (also called a _prefix code_): no
codeword is a prefix of any other.[^clrs-prefix]

Prefix-freeness gives instant, unambiguous decoding: read bits left to right,
and the moment the bits so far match a codeword, that codeword is the _only_
possible symbol, so emit it and start fresh. Restricting to
prefix-free codes costs nothing in compression: for any uniquely decodable code
there is a prefix-free code at least as good, so we lose no optimality by
considering only these.

Every prefix-free code corresponds to a **binary tree**. Symbols sit at the
_leaves_; the path from the root to a leaf spells its codeword, taking `0` for a
left edge and `1` for a right edge. Because symbols are only at leaves, no
codeword can be a prefix of another: a prefix would mean one symbol's leaf lies
on the path to another's, impossible when both are leaves. The **depth** of a
leaf is its codeword's length.

$$
% caption: A prefix-free code as a binary tree. Symbols sit only at leaves; the
%          root-to-leaf path spells the codeword ($0$ left, $1$ right). No codeword is a
%          prefix of another because no leaf lies on the path to another.
\begin{tikzpicture}[level distance=11mm,
  level 1/.style={sibling distance=30mm},
  level 2/.style={sibling distance=16mm},
  inner/.style={draw, circle, minimum size=5mm, inner sep=0pt, fill=black!12},
  leaf/.style={draw, minimum size=7mm, fill=acc!18, font=\small},
  el/.style={font=\scriptsize, midway}]
  \definecolor{acc}{HTML}{2348F2}
  \node[inner] {}
    child {node[leaf] {A} edge from parent node[el, left] {0}}
    child {node[inner] {}
      child {node[leaf] {B} edge from parent node[el, left] {0}}
      child {node[inner] {}
        child {node[leaf] {C} edge from parent node[el, left] {0}}
        child {node[leaf] {D} edge from parent node[el, right] {1}}
        edge from parent node[el, right] {1}}
      edge from parent node[el, right] {1}};
  \node[font=\footnotesize, align=left, anchor=west] at (2.6,-0.6)
    {A $=0$\\ B $=10$\\ C $=110$\\ D $=111$};
\end{tikzpicture}
$$

## The compression problem

Let the alphabet be $C$, and let symbol $c \in C$ occur with frequency
$c.\mathit{freq}$ (its count, or its probability) in the file. In a code tree
$T$, let $d_T(c)$ be the depth of $c$'s leaf, the number of bits in its
codeword. The total number of bits to encode the whole file is the **cost** of
the tree:

$$
B(T) \;=\; \sum_{c \in C} c.\mathit{freq} \cdot d_T(c).
$$

> **Input:** an alphabet $C$ with a frequency $c.\mathit{freq}$ for each
> $c \in C$.
> **Output:** a binary tree $T$ whose leaves are the symbols of $C$, minimizing
> the cost $B(T)$.

> **Property (Optimal trees are full).** An optimal code's tree is always **full**
> — every internal node has exactly two children. (A one-child node wastes a bit:
> promote its subtree and every codeword beneath it shortens.) So with
> $n = \abs{C}$ symbols, an optimal tree has $n$ leaves and exactly $n - 1$
> internal nodes.

## Huffman's algorithm

Huffman's greedy insight is to build the tree _bottom-up_, starting from the
question: which two symbols belong **deepest** in the tree? The two _least
frequent_ ones, since multiplying their long codewords by
small frequencies costs little.[^clrs-huffman] So make the two rarest symbols siblings at the
bottom, merge them into a single "super-symbol" whose frequency is their sum, and
_repeat_ on the smaller alphabet. Each merge fuses two nodes into one, so after
$n - 1$ merges a single tree remains.

A [**min-priority queue**](/algorithms/sorting/heaps-and-heapsort) keyed on
frequency makes "the two least frequent" cheap to extract.

```algorithm
caption: $\textsc{Huffman}(C)$ — build an optimal prefix-free code tree
number: 1
$n \gets \abs{C}$
$Q \gets$ a min-priority queue holding all symbols of $C$, keyed on $\mathit{freq}$
for $i \gets 1$ to $n - 1$ do
  allocate a new internal node $z$
  $z.\mathit{left} \gets x \gets$ $\textsc{Extract-Min}(Q)$ // rarest remaining
  $z.\mathit{right} \gets y \gets$ $\textsc{Extract-Min}(Q)$ // next rarest
  $z.\mathit{freq} \gets x.\mathit{freq} + y.\mathit{freq}$
  call $\textsc{Insert}(Q, z)$ // re-insert merged super-symbol
return $\textsc{Extract-Min}(Q)$ // last node is the root
```

Each iteration removes two nodes and inserts one, shrinking the queue by one; the
single survivor after $n - 1$ rounds is the root of the finished tree. Reading
the tree from the root gives every symbol's codeword.

::impl{algo="huffman#build_huffman_tree"}

## Building a Huffman tree by hand

Take a six-symbol alphabet with these frequencies (in thousands of occurrences),
the classic CLRS example:

| Symbol | `a` | `b` | `c` | `d` | `e` | `f` |
| --- | --- | --- | --- | --- | --- | --- |
| Frequency | 45 | 13 | 12 | 16 | 9 | 5 |

We repeatedly merge the two smallest frequencies:

1. Merge `f`$(5)$ and `e`$(9)$ → node $(14)$.
2. Merge `c`$(12)$ and `b`$(13)$ → node $(25)$.
3. Merge $(14)$ and `d`$(16)$ → node $(30)$.
4. Merge $(25)$ and $(30)$ → node $(55)$.
5. Merge `a`$(45)$ and $(55)$ → root $(100)$.

Each step extracts the two smallest weights and re-inserts their sum, so the
queue loses one element per round until a single root remains.

$$
% caption: The five priority-queue merges that build the Huffman tree. Each step extracts
%          the two least-frequent nodes and inserts their sum; the queue shrinks by one
%          until a single root of weight $100$ remains.
\begin{tikzpicture}[font=\small, yscale=0.9,
  s/.style={draw, circle, minimum size=6mm, inner sep=0pt, fill=acc!18}]
  \definecolor{acc}{HTML}{2348F2}
  \node[font=\footnotesize] at (-0.4,5) {1.};
  \node[s] at (1.0,5) {5}; \node at (1.7,5) {$+$}; \node[s] at (2.4,5) {9};
  \draw[->, thick] (3.0,5) -- (3.7,5); \node[s, fill=acc!30] at (4.4,5) {14};
  \node[font=\footnotesize, anchor=west] at (5.4,5) {queue: 12, 13, 16, 45, {\color{acc}14}};
  \node[font=\footnotesize] at (-0.4,4) {2.};
  \node[s] at (1.0,4) {12}; \node at (1.7,4) {$+$}; \node[s] at (2.4,4) {13};
  \draw[->, thick] (3.0,4) -- (3.7,4); \node[s, fill=acc!30] at (4.4,4) {25};
  \node[font=\footnotesize, anchor=west] at (5.4,4) {queue: 14, 16, 45, {\color{acc}25}};
  \node[font=\footnotesize] at (-0.4,3) {3.};
  \node[s] at (1.0,3) {14}; \node at (1.7,3) {$+$}; \node[s] at (2.4,3) {16};
  \draw[->, thick] (3.0,3) -- (3.7,3); \node[s, fill=acc!30] at (4.4,3) {30};
  \node[font=\footnotesize, anchor=west] at (5.4,3) {queue: 25, 45, {\color{acc}30}};
  \node[font=\footnotesize] at (-0.4,2) {4.};
  \node[s] at (1.0,2) {25}; \node at (1.7,2) {$+$}; \node[s] at (2.4,2) {30};
  \draw[->, thick] (3.0,2) -- (3.7,2); \node[s, fill=acc!30] at (4.4,2) {55};
  \node[font=\footnotesize, anchor=west] at (5.4,2) {queue: 45, {\color{acc}55}};
  \node[font=\footnotesize] at (-0.4,1) {5.};
  \node[s] at (1.0,1) {45}; \node at (1.7,1) {$+$}; \node[s] at (2.4,1) {55};
  \draw[->, thick] (3.0,1) -- (3.7,1); \node[s, fill=acc!40] at (4.4,1) {100};
  \node[font=\footnotesize, anchor=west] at (5.4,1) {root};
\end{tikzpicture}
$$

The resulting tree, with left edges labeled `0` and right edges `1`, is:

$$
% caption: Huffman code tree for the six-symbol example with edges labeled $0$ and $1$.
\begin{tikzpicture}[level distance=12mm,
  level 1/.style={sibling distance=46mm},
  level 2/.style={sibling distance=23mm},
  level 3/.style={sibling distance=14mm},
  inner/.style={draw, circle, minimum size=8mm, font=\small},
  leaf/.style={draw, minimum size=8mm, fill=acc!15, font=\small},
  edglbl/.style={font=\scriptsize, midway, fill=white, inner sep=1.5pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[inner] {100}
    child {node[leaf] {a:45} edge from parent node[edglbl, left] {0}}
    child {node[inner] {55}
      child {node[inner] {25}
        child {node[leaf] {c:12} edge from parent node[edglbl, left] {0}}
        child {node[leaf] {b:13} edge from parent node[edglbl, right] {1}}
        edge from parent node[edglbl, left] {0}}
      child {node[inner] {30}
        child {node[inner] {14}
          child {node[leaf] {f:5} edge from parent node[edglbl, left] {0}}
          child {node[leaf] {e:9} edge from parent node[edglbl, right] {1}}
          edge from parent node[edglbl, left] {0}}
        child {node[leaf] {d:16} edge from parent node[edglbl, right] {1}}
        edge from parent node[edglbl, right] {1}}
      edge from parent node[edglbl, right] {1}};
\end{tikzpicture}
$$

Reading root-to-leaf gives the codewords:

| Symbol | `a` | `b` | `c` | `d` | `e` | `f` |
| --- | --- | --- | --- | --- | --- | --- |
| Codeword | `0` | `101` | `100` | `111` | `1101` | `1100` |

The frequent `a` gets a single bit; the rare `e` and `f` get four. The cost is

$$
B(T) = 45\cdot 1 + 13\cdot 3 + 12\cdot 3 + 16\cdot 3 + 9\cdot 4 + 5\cdot 4 = 224
$$

thousand bits. A fixed-length $3$-bit code would spend
$3 \cdot (45+13+12+16+9+5) = 300$ thousand bits, so Huffman saves about $25\%$, and
no prefix-free code does better.

Encoding concatenates codewords with nothing between them. The word `face`
becomes `1100` `0` `100` `1101`, the eleven-bit stream `11000100 1101`.
Decoding runs the bits back through the tree: start at the root, turn left on `0`
and right on `1`, and the instant a leaf is reached emit its symbol and jump back
to the root. Prefix-freeness is what makes this unambiguous — a leaf is reached
exactly when a whole codeword has been consumed, never mid-codeword.

$$
% caption: Decoding the stream 110001001101 with the example code. Each root-to-leaf
%          descent consumes one codeword; the bits partition uniquely into f, a, c, e with
%          no separators.
\begin{tikzpicture}[xscale=0.92, yscale=0.6, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  % the bit stream, grouped by codeword
  \node[anchor=west] at (0,2) {stream:};
  \foreach \i/\b in {0/1,1/1,2/0,3/0,4/0,5/1,6/0,7/0,8/1,9/1,10/0,11/1} {
    \node[draw, minimum size=5mm, fill=black!5] (bit\i) at (1.6+\i*0.62,2) {\b};
  }
  % group underbraces -> symbols
  \draw[acc, thick] (1.29,1.6) -- (1.29,1.35) -- (3.77,1.35) -- (3.77,1.6);
  \node[acc] at (2.53,1.0) {f = 1100};
  \draw[acc, thick] (3.77,1.6) -- (3.77,1.35) -- (4.39,1.35) -- (4.39,1.6);
  \node[acc] at (4.08,1.0) {a = 0};
  \draw[acc, thick] (4.39,1.6) -- (4.39,1.35) -- (6.25,1.35) -- (6.25,1.6);
  \node[acc] at (5.32,1.0) {c = 100};
  \draw[acc, thick] (6.25,1.6) -- (6.25,1.35) -- (8.73,1.35) -- (8.73,1.6);
  \node[acc] at (7.49,1.0) {e = 1101};
  \node[anchor=west] at (1.6,0.2) {decodes to: f, a, c, e};
\end{tikzpicture}
$$

::impl{algo="huffman#build_codebook+HuffmanCode"}

## Why Huffman is optimal

Huffman is a greedy algorithm, so its proof follows the template from the
previous lesson exactly: a **greedy-choice property** proved by an **exchange
argument**, then **optimal substructure** to close the induction.[^erickson-huffman]

### The greedy choice is safe

> **Lemma (Greedy choice).** Let $x$ and $y$ be the two symbols of lowest
> frequency in $C$. Then some optimal prefix-free code makes $x$ and $y$
> siblings at maximum depth.

> **Proof (exchange argument).** Let $T$ be any optimal tree. Let $a$ and $b$ be
> two sibling leaves at the deepest level of $T$ (a full tree's deepest leaves come
> in sibling pairs). Without loss of generality assume
> $a.\mathit{freq} \le b.\mathit{freq}$ and $x.\mathit{freq} \le y.\mathit{freq}$.
> Since $x$ and $y$ are globally least frequent,
> $x.\mathit{freq} \le a.\mathit{freq}$ and $y.\mathit{freq} \le b.\mathit{freq}$.
>
> Form $T'$ by swapping $x$ with $a$, and $T''$ by then swapping $y$ with $b$. We
> show no swap _increases_ the cost. Moving $x$ down to depth $d_T(a)$ and $a$ up to
> depth $d_T(x)$ changes the cost by
>
> $$
> B(T) - B(T') = \parens{a.\mathit{freq} - x.\mathit{freq}}\parens{d_T(a) - d_T(x)} \ge 0,
> $$
>
> because $a$ is at least as frequent as $x$ ($a.\mathit{freq} - x.\mathit{freq}
> \ge 0$) and $a$ is at least as deep as $x$ ($d_T(a) - d_T(x) \ge 0$). So
> $B(T') \le B(T)$. The same argument gives $B(T'') \le B(T')$. Since $T$ was
> optimal, $T''$ is optimal too, and in $T''$ the symbols $x$ and $y$ are sibling
> leaves at maximum depth. $\qed$

The intuition is the exchange argument in one sentence: _the rarest symbols
belong deepest, so pushing them down and pulling frequent symbols up can never
cost more._

The two swaps are easiest to see side by side. In any optimal tree $T$ the deepest
sibling pair holds some leaves $a, b$; the globally rarest symbols $x, y$ may sit
higher up. Exchanging $x$ with $a$ and $y$ with $b$ sends the rare symbols to the
bottom and lifts the more frequent ones — and the cost only drops, because each
moved-down leaf is rarer and each moved-up leaf is more frequent.

$$
% caption: The greedy-choice exchange for Huffman. Left, an optimal tree $T$ with deepest
%          siblings $a,b$ and the rarest symbols $x,y$ sitting higher. Right, after
%          swapping $x\leftrightarrow a$ and $y\leftrightarrow b$ the rarest symbols are
%          deepest; cost cannot rise since rarer leaves moved down and more frequent
%          leaves moved up.
\begin{tikzpicture}[xscale=0.62, yscale=0.62, font=\small,
  inner/.style={draw, circle, minimum size=4mm, inner sep=0pt, fill=black!12},
  leaf/.style={draw, minimum size=6mm, inner sep=1pt, fill=acc!15},
  moved/.style={draw=acc, very thick, minimum size=6mm, inner sep=1pt, fill=acc!15}]
  \definecolor{acc}{HTML}{2348F2}
  \useasboundingbox (-0.8,-1.5) rectangle (12.0,4.4);
  % ---------- left tree T (before) ----------
  \node[font=\footnotesize] at (-0.2,4.0) {tree $T$};
  \node[inner] (r) at (1.3,3.4) {};
  \node[leaf] (x) at (0.0,2.0) {$x$};       % rare, sits shallow
  \node[inner] (m) at (2.6,2.0) {};
  \node[leaf] (y) at (1.6,0.6) {$y$};        % rare, sits shallow-ish
  \node[inner] (n) at (3.4,0.6) {};
  \node[leaf] (a) at (2.7,-0.8) {$a$};       % deepest sibling pair
  \node[leaf] (b) at (4.1,-0.8) {$b$};
  \draw (r)--(x); \draw (r)--(m); \draw (m)--(y); \draw (m)--(n);
  \draw (n)--(a); \draw (n)--(b);
  % ---------- right tree T'' (after) ----------
  \begin{scope}[xshift=7.0cm]
    \node[font=\footnotesize] at (-0.2,4.0) {after swaps};
    \node[inner] (r2) at (1.3,3.4) {};
    \node[leaf] (a2) at (0.0,2.0) {$a$};
    \node[inner] (m2) at (2.6,2.0) {};
    \node[leaf] (b2) at (1.6,0.6) {$b$};
    \node[inner] (n2) at (3.4,0.6) {};
    \node[moved] (x2) at (2.7,-0.8) {$x$};   % rarest now deepest
    \node[moved] (y2) at (4.1,-0.8) {$y$};
    \draw (r2)--(a2); \draw (r2)--(m2); \draw (m2)--(b2); \draw (m2)--(n2);
    \draw (n2)--(x2); \draw (n2)--(y2);
  \end{scope}
  % swap arrow between panels
  \draw[->, red!75!black, very thick] (4.9,1.0) -- (6.3,1.0)
    node[midway, above, font=\footnotesize] {swap $x$/$a$,};
  \node[red!75!black, font=\footnotesize] at (5.6,0.3) {$y$/$b$};
\end{tikzpicture}
$$

### Optimal substructure

> **Lemma (Substructure).** Let $z$ be the super-symbol replacing siblings $x, y$,
> with $z.\mathit{freq} = x.\mathit{freq} + y.\mathit{freq}$, and let $C'$ be the
> alphabet with $x, y$ replaced by $z$. Any optimal tree $T'$ for $C'$ extends to
> an optimal tree $T$ for $C$ by replacing $z$'s leaf with an internal node whose
> children are $x$ and $y$.

> **Proof.** When the leaf $z$ at depth $d$ in $T'$ becomes an internal node with
> children $x, y$ at depth $d+1$, the cost changes by a fixed amount independent of
> the tree:
>
> $$
> B(T) = B(T') + \parens{x.\mathit{freq} + y.\mathit{freq}},
> $$
>
> since $x$ and $y$ each sit one level below where $z$ sat, while $z$ itself
> (weight $x.\mathit{freq}+y.\mathit{freq}$) leaves the sum. Now suppose, for
> contradiction, that some tree $T^\star$ for $C$ beats $T$. By the greedy-choice
> lemma we may assume $x, y$ are siblings in $T^\star$; merging them into a single
> leaf $z$ yields a tree for $C'$ of cost
> $B(T^\star) - (x.\mathit{freq}+y.\mathit{freq}) < B(T') $, contradicting the
> optimality of $T'$. Hence $T$ is optimal. $\qed$

Together the two lemmas give the theorem by induction on $\abs{C}$.

> **Theorem (Huffman optimality).** $\textsc{Huffman}$ produces an optimal
> prefix-free code.

> **Proof.** Induct on $\abs{C}$. The base case of one symbol is trivial. For the
> inductive step, each merge is both _safe_ (the greedy-choice lemma puts the two
> rarest symbols deepest in some optimal tree) and _composable_ (the substructure
> lemma extends an optimal tree for the merged alphabet $C'$ to an optimal tree for
> $C$). So the tree built by $n-1$ merges is optimal. $\qed$

## Running time

The cost is dominated by the priority-queue operations. Building the initial
min-heap from $n$ symbols takes $O(n)$. The loop runs $n - 1$ times, and each
iteration does two $\textsc{Extract-Min}$s and one **Insert**, each $O(\log n)$ on a
binary heap. Hence

$$
T(n) = O(n) + (n-1)\cdot O(\log n) = O(n \log n).
$$

If the frequencies arrive already sorted, two simple FIFO queues replace the heap
(one of original leaves, one of merged nodes, both kept in nondecreasing
frequency), and each "extract two smallest" is $O(1)$, giving an $O(n)$
algorithm. The $O(n\log n)$ bound, like activity selection's, is really the cost
of getting the symbols into sorted order.

::impl{algo="huffman#two_queue_huffman_tree"}

## Entropy, arithmetic coding, and the whole-bit floor

Huffman coding is optimal among codes that assign each symbol a _whole number_
of bits independently. This section places it against the theoretical floor and
against the codes that go beyond it.

**The entropy bound.** Shannon's source coding theorem (1948) sets the floor: no
uniquely decodable code can average fewer than the **entropy**
$H = \sum_c p_c \log_2(1/p_c)$ bits per symbol, and a Huffman code always lands
within one bit of it, $H \le \bar{L}_{\text{Huffman}} < H + 1$.[^shannon] The
example above illustrates the gap: its entropy is about $2.24$ bits per symbol
while Huffman spends $\bar{L} = 224/100 = 2.24$ — essentially on the floor,
because the frequencies are close to powers of $\tfrac12$. The one-bit slack
becomes visible only on _skewed_ sources.

**The whole-bit floor.** When a symbol's ideal codeword length $\log_2(1/p)$ is
fractional — for a symbol of probability $0.9$, ideally $0.15$ bits — Huffman must
round up to a full bit, wasting the difference. **Arithmetic coding** (Rissanen &
Langdon, 1979) sidesteps the integer-bit floor by encoding the _entire message_ as
a single fraction in $[0,1)$, so a symbol can cost a fractional number of bits and
the total approaches $H$ arbitrarily closely.[^arith] Modern **asymmetric numeral
systems** (Duda, 2009) match arithmetic coding's ratio at Huffman-like speed and
are now used in Zstandard, LZFSE, and JPEG XL.[^ans]

$$
% caption: Where Huffman sits. The entropy $H$ is the hard floor (Shannon); Huffman lands
%          within one bit of it, tight on near-dyadic sources and slack on skewed ones;
%          arithmetic coding / ANS close the remaining gap toward $H$.
\begin{tikzpicture}[font=\small, >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{grn}{HTML}{1A8A3B}
  \draw[->, thick] (0,0) -- (9.2,0) node[right, font=\footnotesize] {bits/symbol};
  % entropy floor
  \draw[grn, very thick] (2.0,-0.35) -- (2.0,0.9);
  \node[grn, font=\footnotesize, anchor=south] at (2.0,0.9) {entropy $H$};
  % Huffman band: within +1 bit
  \fill[acc!14] (2.0,-0.2) rectangle (5.2,0.55);
  \draw[acc, thick] (2.0,-0.2) rectangle (5.2,0.55);
  \node[acc, font=\footnotesize, anchor=south] at (3.6,0.55) {Hu\/f\/fman: $[H,\,H{+}1)$};
  % arithmetic/ANS: hugs H
  \draw[black, thick, dashed] (2.35,-0.35) -- (2.35,0.35);
  \node[black, font=\footnotesize, anchor=west, align=left] at (5.5,0.55)
    {arithmetic / ANS\\ hug the f\/loor $H$};
\end{tikzpicture}
$$

**Where it is still used.** Huffman's simplicity, speed, and provable optimality
within its class keep it embedded in DEFLATE (gzip, PNG, ZIP), JPEG, and MP3 to
this day, usually as the final entropy-coding stage after a modeling transform.
Two engineering variants matter in practice: **canonical Huffman codes** store the
codebook as just the per-symbol lengths (the codewords are then reconstructed by a
fixed rule), shrinking the header DEFLATE must transmit; and **length-limited
Huffman** (the Package-Merge algorithm of Larmore & Hirschberg, 1990) caps the
maximum codeword length so decode tables stay small, at a tiny cost in
ratio.[^pkgmerge] Huffman remains the textbook proof that a greedy algorithm,
properly justified, can be _exactly_ optimal, not merely a good heuristic.

## Takeaways

- A **prefix-free code** lets a stream decode unambiguously — it is a
  binary tree with symbols at the leaves, codeword length = leaf depth.
- The goal is to minimize $B(T) = \sum_c c.\mathit{freq}\cdot d_T(c)$; optimal
  trees are **full**.
- **Huffman's algorithm** greedily merges the two least-frequent nodes via a
  min-priority queue, $n-1$ times, building the tree bottom-up.
- Optimality follows the greedy template: an **exchange argument** shows the
  rarest symbols belong deepest (greedy choice), and **optimal substructure**
  closes the induction.
- Running time is $O(n\log n)$, the cost of the heap operations, dropping to
  $O(n)$ when frequencies are pre-sorted.

[^skiena-huffman]: **Skiena**, §5 — Data Compression: Huffman's greedy construction of the optimal variable-length code for a given file.
[^clrs-prefix]: **CLRS**, Ch. 16 — Greedy Algorithms (§16.3): prefix-free codes and their representation as binary trees with symbols at the leaves.
[^clrs-huffman]: **CLRS**, Ch. 16 — Greedy Algorithms (§16.3): the greedy rule of repeatedly merging the two least-frequent symbols, implemented with a min-priority queue.
[^erickson-huffman]: **Erickson**, Ch. 4 — Greedy Algorithms (Huffman Codes): the optimality proof via greedy-choice exchange plus optimal substructure.
[^shannon]: **Shannon, C. E.** (1948), "A mathematical theory of communication," _Bell System Technical Journal_ 27, 379–423 & 623–656 — entropy $H$ as the lower bound on average code length; a Huffman code satisfies $H \le \bar{L} < H+1$.
[^arith]: **Rissanen, J. & Langdon, G. G.** (1979), "Arithmetic coding," _IBM Journal of Research and Development_ 23(2), 149–162 — encoding a whole message as one interval, escaping Huffman's whole-bit-per-symbol floor.
[^ans]: **Duda, J.** (2009), "Asymmetric numeral systems," arXiv:0902.0271 — near-entropy compression at table-lookup speed, now used in Zstandard, LZFSE, and JPEG XL.
[^pkgmerge]: **Larmore, L. L. & Hirschberg, D. S.** (1990), "A fast algorithm for optimal length-limited Huffman codes," _Journal of the ACM_ 37(3), 464–473 — the Package-Merge algorithm building optimal Huffman codes under a maximum-length constraint.