GreedyGreedy

Huffman Coding

Build an optimal prefix-free binary code by repeatedly merging the two least frequent symbols with a min-heap.

Text to encode — A short string; its character frequencies drive the tree. 6-20 characters works best.

Frequencies

symbol	count
c	1
d	1
b	2
r	2
a	5

Priority queue (lowest weight first)

node	weight
c	1
d	1
b	2
r	2
a	5

1/17"abracadabra" is 11 characters drawn from 5 distinct symbols. A fixed-width code would spend 3 bits on every character regardless of how often it appears; Huffman's idea is to spend fewer bits on the common symbols and more on the rare ones, and to do it optimally rather than by hand.

One of the two lowest-weight nodesMerged parent just createdRoot-to-leaf path being read as a codeSymbol whose code is fixed

PseudocodeLearn Huffman Coding →

1count the frequency of every symbol
2push one leaf per symbol into a min-heap keyed by frequency
3while the heap holds more than one node:
4  a = pop()                       # lowest frequency
5  b = pop()                       # second lowest
6  push(node(weight = a.w + b.w, left = a, right = b))
7root = pop()
8walk down assigning codes: left edge = 0, right edge = 1

Variables

characters11

distinctSymbols5

fixedWidthBits33

Complexity

worst O(n log n)

space O(n)

Speed