Huffman Coding

Builds an optimal variable-length prefix code from symbol frequencies. Repeatedly merging the two least-frequent nodes into a new tree (using a min-heap) guarantees frequent symbols end up with the shortest codes.

Category: Greedy
Time complexity: O(n log n)
Space complexity: O(n)

Pseudocode

put every symbol in a min-heap by frequency
pop the two smallest, merge into one node
push the merged node back
repeat until one tree remains

Reference implementation

heap = [Node(f, ch) for ch, f in freqs]
while len(heap) &gt; 1:
    a, b = heappop(heap), heappop(heap)
    heappush(heap, Node(a.f + b.f, l=a, r=b))

Open the interactive Huffman Coding visualisation →