Greedy Algorithms

Huffman Coding

Huffman coding is a greedy algorithm that constructs an optimal code for compressing a given string.

Steps

1. Represent each character of the string by a node with weight = # times character occurs in the string.
2. Combine two nodes with minimum weights into new node with weight = sum of the weights of the original nodes.
3. Repeat step 2 until all nodes have been combined