Huffmann Algorithm

Suppose a list of n weights is given as w1, w2, w3 … wn. Among all the 2-trees with ’n’ weights, find a tree T with a minimum — weighted path length.

Huffmann Algorithm

The basic idea of this algorithm is to keep the lightest weightnodes farthest from the root node R and the heaviest weight nodes are closer to the root.

This way when multiplied, the greater pathlengths are multiplied with the lighter nodes, making the entire path length smaller by comparison.

Let’s take an example to understand this better -

These are the sample nodes and their respective weights from which we need to formulate a tree which gives minumum- weighted path length.

STEP.1 : Take the 2 minimum weights in the list. Here is it E and H.

STEP.2 : Make a subtree of them both.

In the root node of this subtree, sum of both the nodes are written.

STEP.3 : See which is the next minimum node ( 5 and 2 are replaced by 7 in the list). We have 5 and 7 as the next minimum. Make a subtree out of them.

STEP 4: Now, replace 12 instead of 7 and 5 in the list and continue comparing. Next smallest weights are 11 and 11. So form a separate sub tree for that.

(I think at this point, it is clearly visible how much this writer is struggling with paint (ง •_•)ง)

STEP 5 : Replace 22 instead of 11 and 11 in the list. Now, next smallest is 12 and 19. Connect them to make a subtree.

STEP 6: The next in line will be 22 and 22, connect them both

STEP 7: Next, 25 and 31 are the smallest in the list, so connect them both and make a subtree. Similarily, in the next step, 56 and 44 are the ones left, so connect them up and form the root node 100. Continue the above procedure till you get all the nodes linked into the tree. (Basically, this is where the writer looses patience in her paint application 😬😂)

FINAL ALGORITHM

One thing you would have noticed is that above steps are actually a repetition of one basic function.

Suppose w1 and w2 are two minimum weights among the ’n’ given weights w1,w2…wn. Find a tree T which gives a solution for the n-1 weights i.e w1+w2, w3, w4, … wn.

Then, in the tree T replace the external node w1+w2 by a subtree and recurse the function.