Frequent symbols should use shorter codewords
Huffman coding repeatedly combines the two least-frequent nodes into a binary tree. Leaf paths become prefix-free codes, so no complete codeword is the prefix of another.
For frequencies A:5, B:2, C:1, D:1, first combine C and D into weight two. Combine that node with B into weight four, then combine it with A. One resulting assignment is A=0, B=10, C=110, D=111, with weighted length 5×1 + 2×2 + 1×3 + 1×3 = 15 bits. Left/right choices and tie-breaking can produce different equally good codes.
A minimum-priority queue builds the tree in O(k log k) for k distinct symbols. Encoding must also account for the input length and the stored codebook. Tiny inputs may grow after metadata overhead.
Exercise
Build a frequency table, tree, encoder, and decoder. Verify round-trip equality for empty input, a single repeated symbol, and several tied frequencies. Define an explicit representation for the single-symbol case.
Check: prefix-free coding solves decodability; corruption detection, framing, Unicode representation, and codebook serialization are separate requirements.