EXAMPLE 10 Huffman Code

To illustrate the Huffman method, say we have six letters of a dataset that occur with the following probabilities:

Rearranging them in increasing order, we have:

Because and are the two letters least likely to occur, we begin our tree by merging them with the one with the smallest probability on the left (i.e., rather than ), adding their probabilities, and rearranging the resulting items in increasing order:

This time, and are the two least likely remaining entries, so we merge them with on the left (because it has smallest probability), add their probabilities, and re-sort from smallest to largest. This gives:

Next, we combine and with on the left and re-sort to get:

Then we combine and with on the left and re-sort again:

And finally we combine and with on the left to obtain: