Huffman Coding for Frequencies

Characters: T43, I38, V16, K8, L50, E12, O56, Z13, P22, R7 → total 265

Huffman Algorithm (Greedy, min-heap)

repeat n-1 times: extract two smallest nodes x,y, create z with freq=f_x+f_y, insert z, make x,y children of z

Tree built bottom-up, codes derived by 0/1 left/right.

Step-by-Step Merging (sorted order)

Initial heap (freq, char): R7, K8, E12, Z13, V16, P22, I38, T43, L50, O56

1. R7+K8=15 (RK15)
2. E12+Z13=25 (EZ25)
3. RK15+V16=31 (RKV31)
4. P22+EZ25=47 (PEZ47)
5. RKV31+I38=69 (RKVI69)
6. T43+PEZ47=90 (TPEZ90)
7. L50+O56=106 (LO106)
8. RKVI69+TPEZ90=159 (RKVI-TPEZ159)
9. LO106+RKVI-TPEZ159=265 (root)

(Different tie orders produce different but equally optimal trees; one valid complete merge sequence above.)

Build Tree & Codes (example labeling left=0, right=1)

One optimal prefix code (lengths depend on exact merging order):

• R: 00000 (7)
• K: 00001 (8)
• V: 0001 (16) ← combined with RK
• E: 0010 (12)
• Z: 0011 (13)
• P: 010 (22)
• I: 011 (38)
• T: 100 (43)
• L: 101 (50)
• O: 11 (56) shortest for highest frequency

Exact bit strings vary by left/right assignment; what matters is code lengths: Len: O2, L3, T3, I3, P3, E4, Z4, V4, K5, R5 (or similar optimal 2-5 bits). Canonical Huffman would give same lengths.

Weighted Path Length

$$WPL = \sum f_i \cdot l_i = 56·2 + 50·3 + 43·3 + 38·3 + 22·3 + 16·4 +13·4 +12·4 +8·5 +7·5 = 112+150+129+114+66+64+52+48+40+35 = 810 \text{ bits}$$ (approx, exact depends on lengths 2 vs3 for L/O). Average bits/char = 810/265 ≈3.06 (vs fixed 4 bits for 10 symbols). Compression saves ~23%.

Properties

• Prefix-free (no code is prefix of another), optimal among prefix codes (proven by greedy exchange).
• Time $O(n \log n)$ with heap ($n$ symbols), space $O(n)$.
• Decoding via tree traversal.