Greedy problems — activity selection, fractional knapsack, Huffman coding (full algorithm): Visual walkthrough

We only touch the parent topic's Huffman section, and lean on three helpers when they appear: Priority Queue / Binary Heap (the machine that hands us the smallest item), Exchange Argument (the proof style), and Prefix Codes & Information Theory (what a "code" even is).

Step 1 — What is a code? A tree of yes/no questions

WHAT. We draw every prefix-free code as a binary tree. Start at the top (the root). Going left writes a 0; going right writes a 1. Each symbol lives at a leaf (a bottom node with no children). Its codeword is the sequence of turns from root down to it.

WHY a tree and not a list? Because "prefix-free" is exactly "every symbol is a leaf." If a symbol sat at an internal node, its bit-string would be the prefix of everything below it — ambiguous. The tree makes the prefix rule automatic and visible.

PICTURE. Below, follow the amber path root→left→right→left: that spells the codeword 010. No symbol sits on that path except at its very end.

Figure — Greedy problems — activity selection, fractional knapsack, Huffman coding (full algorithm)

Step 2 — What are we minimizing? Total bits sent

WHAT. Add that up over all symbols. That total is the number we fight to shrink: $Cost = \sum_{i} how often symbol i appears f_{i} \times bits in its codeword ℓ_{i}$

WHY this formula and not just "shortest codewords"? Because a rare symbol with a long codeword barely hurts (small $f_{i}$ ), while a common symbol with a long codeword is a disaster (large $f_{i}$ ). The product $f_{i} ℓ_{i}$ captures the trade-off exactly: it's the total bandwidth this symbol eats.

PICTURE. Below, each leaf's column shows $f_{i}$ (a bar) times $ℓ_{i}$ (its depth). The message cost is the sum of the shaded areas — we want the smallest total shaded area.

Step 3 — A cleaner way to count the cost: sum the internal nodes

WHAT. There's a second way to compute the exact same Cost, and it's the key to the proof. Give every internal node (a node with children) a frequency equal to the sum of all leaf-frequencies beneath it. Claim: $Cost = \sum_{internal nodes v} total frequency of leaves under v g_{v}$

WHY is this true? Look at any single leaf $i$ at depth $ℓ_{i}$ . To reach it from the root you pass through exactly $ℓ_{i}$ internal nodes (one per edge down). So $f_{i}$ gets counted once inside each of those $ℓ_{i}$ internal-node sums. Total times $f_{i}$ is counted $= ℓ_{i}$ . That's precisely $f_{i} ℓ_{i}$ — the same contribution as before. Summing over all leaves gives the same Cost, just bookkept differently.

PICTURE. The amber leaf's frequency flows up the tree; every internal node it passes through has that frequency added to its running total. Count the up-arrows: that's the depth.

Reading of cost identity

Total bits = sum over internal nodes of (combined frequency below that node), because each symbol's frequency is counted once per level of depth.

Step 4 — The greedy move: glue the two smallest, and recurse

WHAT. Put all $n$ symbols into a min-heap keyed by frequency. Repeat: pop the two smallest, $a$ and $b$ ; make a new node with frequency $f_{a} + f_{b}$ and children $a, b$ ; push it back. After $n - 1$ merges one node remains — the root.

WHY the two smallest? Step 3 said each merge charges its combined frequency to the Cost. To keep the running bill low, each merge should combine the two cheapest available frequencies. Also, whichever two we merge first become the deepest leaves in the final tree (they get pushed down by every later merge above them) — so the smallest frequencies rightly land deepest, matching Step 2's tension.

PICTURE. Watch one merge: the two shortest bars (amber) leave the heap and reappear as one taller bar; the heap reorders.

Step 5 — WHY this is optimal: the exchange picture

This is the heart. We use an Exchange Argument: take any optimal tree and show our greedy choice never makes it worse.

WHAT. Let $a, b$ be the two lowest-frequency symbols. Take any optimal tree $T^{⋆}$ . Somewhere in it, at the deepest level, sit two sibling leaves — call them $x, y$ (a deepest node always has a sibling in a well-formed code tree). Now swap: move $a$ down into $x$ 's spot and $x$ up into $a$ 's spot; same for $b, y$ .

WHY the swap can't hurt. Consider swapping $a$ (frequency $f_{a}$ , old depth $d_{a}$ ) with $x$ (frequency $f_{x}$ , old depth $d_{x}$ ). Only these two leaves change depth, so the Cost change is: $Δ = \leq 0 since a is a smallest freq (f_{a} - f_{x}) \times \geq 0 since x is deepest (d_{x} - d_{a}) \leq 0$

$f_{a} - f_{x} \leq 0$ : $a$ is one of the two smallest frequencies, so it is $\leq f_{x}$ .
$d_{x} - d_{a} \geq 0$ : $x$ sits at the deepest level, so it is $\geq$ any other depth.
A non-positive times a non-negative is non-positive — the swap cannot increase Cost.

So there exists an optimal tree in which $a, b$ are the deepest siblings — exactly the pair our greedy step merges. Greedy is safe. Then delete $a, b$ , treat their parent as a new leaf of frequency $f_{a} + f_{b}$ , and the same argument runs on a smaller problem (optimal substructure) until the tree is built. $□$

PICTURE. Left: an optimal tree with a frequent symbol stuck deep and a rare one shallow. Right: after swapping, the rare one is deep, frequent one shallow — the amber Cost bar shrinks or ties, never grows.

Step 6 — Edge and degenerate cases

Every scenario must be covered, or the reader trips on the one you skipped.

Definition The corner cases, each resolved

One symbol ( $n = 1$ ). No merges happen. Convention: give it the single codeword 0 (length 1). Cost $= f_{1} \cdot 1$ . A tree of one leaf has depth-1 by convention so the file isn't zero-length-encoded.
Two symbols ( $n = 2$ ). One merge: 0 and 1, each length 1. Cost $= f_{1} + f_{2}$ (their combined frequency = the single internal node). Optimal trivially.
Ties in frequency. The heap may pop either equal-frequency item first. Different tie-breaks give different trees but identical Cost — the Step-5 inequality only used $\leq$ , so ties don't break optimality.
A dominant symbol (one $f_{i}$ larger than all others combined). It gets merged last, ending up at depth 1 with codeword length 1 — exactly right for the most frequent symbol.
Zero-frequency symbol. It still needs a codeword; it merges first (smallest), lands deepest, contributes $0$ to Cost. Harmless.

PICTURE. Two extreme skylines side by side: a balanced tree (all frequencies near-equal → near-equal depths) and a skewed tree (one huge frequency → a long thin comb). Both are Huffman-optimal for their frequencies.

The one-picture summary

Everything at once: the heap feeds the smallest pair into a merge, the merge adds its combined frequency to the Cost tally, the tree grows downward, and the exchange argument guarantees the smallest frequencies end up deepest — so the total shaded Cost is as small as any tree allows.

Recall Feynman: retell the whole walkthrough in plain words

Imagine you're inventing short secret-codes for words. A code is just a tree of left/right turns, and each word sits at the bottom — a leaf. How deep a word is = how long its code is (Step 1). You want to send the fewest total bits, so you pay "how often × how long" for each word and add it up (Step 2). Here's the trick: that same total equals adding up the sizes of every branch-point in the tree — because each word's count gets tallied once for every level it sits below (Step 3). So to keep the bill low, every time you fuse two words into a branch, you should fuse the two rarest ones — the cheapest possible fusion — and those two sink to the bottom, getting the longest codes (Step 4). Why is grabbing-the-rarest always optimal? Take any best-possible tree; the two rarest words might not be at the bottom, but if you swap them down there, you're pushing small numbers deeper and pulling big numbers up — that can only save bits, never waste them (Step 5). Handle the tiny cases (one word, two words, ties, a giant word) and you're done (Step 6). Frequent words get short codes, rare words get long ones, and no arrangement beats it.