Algorithm for Huffman code

Huffman's algorithm is greedy: repeatedly join the two lowest-weight trees until only one tree remains.

HuffmanCode(symbols[1..n], freq[1..n])
1. For each symbol create a leaf node with its frequency
   and insert all leaves in a priority queue Q (min-heap on frequency).
2. For i = 1 to n-1:
      a. x = ExtractMin(Q)               (smallest weight)
      b. y = ExtractMin(Q)               (next smallest)
      c. create a new node z:
             z.left   = x
             z.right  = y
             z.weight = x.weight + y.weight
      d. Insert z into Q
3. The one node left in Q is the root of the Huffman tree.
4. Traverse the tree from the root: append 0 when going to the
   left child and 1 when going to the right child. The path to a
   leaf is the code of that symbol.

Pseudo-code for code assignment:

Assign(node, code)
   if node is a leaf: code(node.symbol) = code
   else: Assign(node.left,  code + "0")
         Assign(node.right, code + "1")

Complexity: with a heap each insertion/extraction costs O(log n), and the loop performs about 3n of them (2(n − 1) extractions and n − 1 insertions), so the total is O(n log n). A sorted list gives O(n²).