Data Structures and Algorithms


Operation of the Huffman algorithm

Initial data sorted by frequency
Combine the two lowest frequencies,
F and E, to form a sub-tree
of weight 14.

Move it into its correct place.

Again combine the two lowest frequencies,
C and B, to form a sub-tree
of weight 25.

Move it into its correct place.

Now the sub-tree with weight, 14, and D are combined to make a tree of weight, 30.

Move it to its correct place.

Now the two lowest weights are held by the "25" and "30" sub-trees, so combine them to make one of weight, 55.

Move it after the A.

Finally, combine A and the tree to make the final encoding tree.

Mark the left branches with "0" and the right branches with "1" to give the encodings:



Table of Contents
© John Morris, 1996