Huffman coding

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Fractional knapsack greedy rule? from Lesson 4.2.2
• Activity selection complexity? from Lesson 4.2.1
• Heap operations insert/extract cost? from Lesson 0.2.2

1 · The Hook

🎣

ASCII spends 8 bits on every character, whether it is the common "e" or the rare "z". Give frequent symbols short codes and rare ones long codes, and files shrink. Huffman's greedy algorithm builds the best possible such code, and GATE asks for code lengths and average bits.

2 · Predict First

🤔

Frequencies: a 45, b 13, c 12, d 16, e 9, f 5. Huffman repeatedly merges the two smallest weights. Which two are merged first, and what is the new weight?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

The two smallest are f (5) and e (9): merged into a node of weight 14.

Prefix codes

A code is prefix-free if no codeword is a prefix of another, so a bit string decodes uniquely left to right. Prefix codes correspond to binary trees: symbols at leaves, left edge 0, right edge 1; codeword length = depth of the leaf.

Cost of a code = Σ frequency × codeword length (total bits). Average length = cost ÷ Σ frequencies.

Huffman's algorithm

• Put every symbol in a min-priority queue keyed by frequency.

• Repeat n − 1 times: remove the two smallest, create a parent with weight = their sum, insert the parent.

• The last node is the root.

• Θ(n log n) with a heap.

• Optimal: no prefix code has a smaller cost (greedy-choice: the two rarest symbols can be siblings at the deepest level).

• Cost = sum of all merge weights (each merge adds one bit to every symbol beneath it).

Worked example

a 45, b 13, c 12, d 16, e 9, f 5 (total 100):

• f + e = 14; c + b = 25; 14 + d = 30; 25 + 30 = 55; a + 55 = 100.
• Lengths: a 1; b, c, d 3; e, f 4.
• Cost = 45·1 + (13 + 12 + 16)·3 + (9 + 5)·4 = 45 + 123 + 56 = 224 = 14 + 25 + 30 + 55 + 100.
• Average 2.24 bits per symbol, versus 3 bits for a fixed-length code of 6 symbols.

Ties may produce different trees, but every Huffman tree has the same optimal cost.

4 · Visual

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

5 · Worked Examples

Example 1 Easy

Is {0, 10, 110, 111} prefix-free? Is {0, 01, 11}?

Solution

Yes; no (0 is a prefix of 01).

Example 2 Medium

Frequencies p 5, q 25, r 7, s 15, t 4, u 12. Total bits of the Huffman code?

Solution

Merges: 4 + 5 = 9; 7 + 9 = 16; 12 + 15 = 27; 16 + 25 = 41; 27 + 41 = 68. Cost = 9 + 16 + 27 + 41 + 68 = 161.

Example 3 GATE

Symbols with frequencies A 10, B 15, C 12, D 3, E 4, F 13, G 1 (total 58). Average codeword length of a Huffman code (2 decimals)?

Solution

Merges: 1 + 3 = 4; 4 + 4 = 8; 8 + 10 = 18; 12 + 13 = 25; 15 + 18 = 33; 25 + 33 = 58. Cost = 146; average 146/58 ≈ 2.52.

6 · GATE Traps

⚠️

• Always merge the two smallest current weights (including merged nodes).
• Cost = Σ merge weights; average = cost ÷ total frequency.
• Ties change the codes, not the total cost.
• Huffman is optimal among prefix codes with symbol-by-symbol coding.

7 · Memory Hook

🧠

"Merge the two rarest; the bill is the sum of merges."

8 · Connect the Dots

Huffman merges the two smallest repeatedly. The same rule merges sorted files cheapest (next lesson), which also collects the cases where greedy does not work.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markFirst merge

Frequencies a 45, b 13, c 12, d 16, e 9, f 5. Weight of the second merged node created by Huffman's algorithm?

Numerical answer: ________

Q2NAT2 marksCost

Frequencies a 45, b 13, c 12, d 16, e 9, f 5. Total Huffman cost (Σ frequency × length)?

Numerical answer: ________

Q3NAT2 marksAverage length

Frequencies 0.4, 0.3, 0.2, 0.1 for four symbols. Average Huffman codeword length?

Numerical answer: ________

Q4MCQ1 markPrefix-free

Which set is prefix-free?

• (A) {00, 01, 0}
• (B) {0, 01, 10}
• (C) {1, 01, 001, 000}
• (D) {10, 101, 11}

Q5NAT2 marksLongest code

Frequencies A 10, B 15, C 12, D 3, E 4, F 13, G 1. Length of the longest Huffman codeword?

Numerical answer: ________

10 · Rule Card

• Prefix-free code ↔ binary tree; length = depth.
• Huffman: repeatedly merge the two smallest weights; Θ(n log n); optimal.
• Cost = Σ f·len = Σ merge weights; average = cost / Σ f.
• Ties: different codes, same cost.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

prefix-free codecode treecodeword length = depthHuffman's algorithmcost as sum of mergesaverage codeword length

12 · Answer Vault