Huffman codes

Algorithm to contruct a Huffman code

HUFFMAN(C)
    n = |C|
    Q = C
    for i = 1 to n - 1
        allocate a new node z
        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)

Common options of implementation

• mean-heap: O(n log n)
• van Emde Boas: O(n log log n)

Reference(s)

• T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 3rd ed. Cambridge, MA: The MIT Press, 2009.