Type the Huffman algorithm (CLRS HUFFMAN)

Answer

HUFFMAN(C) n = |C| Q = BUILD-MIN-HEAP(C) // keyed by frequency for i = 1 to n - 1 z = ALLOCATE-NODE() z.left = x = EXTRACT-MIN(Q) z.right = y = EXTRACT-MIN(Q) z.freq = x.freq + y.freq INSERT(Q, z) return EXTRACT-MIN(Q) // the root

Start with a min-heap of the n character nodes. Each iteration merges the two lowest-frequency nodes into a parent whose frequency is their sum, doing n-1 merges total. BUILD-MIN-HEAP is O(n); n-1 iterations x O(lg n) per heap op gives O(n lg n).