Building the Huffman Tree

Huffman's 1952 algorithm: given symbol frequencies, build a tree where:

• Each leaf is a symbol
• Each path root->leaf encodes the symbol as a sequence of bits
• More frequent symbols get shorter codes

The construction is famously simple:

1. Start with each symbol as a leaf node, key = frequency.
2. Place all leaves in a min-priority-queue.
3. Repeat until 1 node remains:
   a. Pop the two smallest-frequency nodes A and B.
   b. Create a parent node with frequency = A.freq + B.freq.
   c. Set A as left child, B as right child.
   d. Push the parent back into the queue.
4. The remaining node is the root.

Example: frequencies {a:5, b:9, c:12, d:13, e:16, f:45}.

Iteration 1: pop a(5), b(9) -> parent(14). Queue: [c:12, d:13, p1:14, e:16, f:45]
Iteration 2: pop c(12), d(13) -> p2(25). Queue: [p1:14, e:16, p2:25, f:45]
Iteration 3: pop p1(14), e(16) -> p3(30). Queue: [p2:25, p3:30, f:45]
Iteration 4: pop p2(25), p3(30) -> p4(55). Queue: [f:45, p4:55]
Iteration 5: pop f(45), p4(55) -> root(100). Queue: [root:100]

Final codes (assigning 0=left, 1=right):

a: 1100  (4 bits)   - rare
b: 1101  (4 bits)
c: 100   (3 bits)
d: 101   (3 bits)
e: 111   (3 bits)
f: 0     (1 bit!)   - most common, shortest code

Notice how f (most frequent) got 1 bit while a (least frequent) got 4. That's Huffman's optimality.