Steps to build Huffman Tree
Input is array associated with unique characters with their frequency associated with occurrences as well as output is Huffman Tree.
Step-1: Make a leaf node for every unique character as well as develop a min heap of all leaf nodes.
Step-2: Get two nodes using the minimum frequency from the min heap.
Step-3: Make a new internal node together with frequency corresponding to the sum the two nodes frequencies. Help make the initial extracted node as its left child and the other extracted node because it's right child. Include this particular node to the min heap.
Step-4: Do it again steps2 and steps3 prior to the heap consists of just one node. The remaining node may be the root node and the tree is complete.
For Example:
| Character | Frequency |
|---|---|
| a | 5 |
| b | 9 |
| c | 12 |
| d | 13 |
| e | 16 |
| f | 45 |
Step1: Make a min heap which has 6 nodes exactly where every node signifies root of a tree along with single node.
Step2: Get two minimum frequency nodes through min heap. Put in a new internal node together with frequency i.e. the result of (5+9=14).
At this point min heap has 5 nodes where by 4 nodes usually are sources connected with trees having single element each, and another heap node is usually root of tree having 3 elements.
| Character | Frequency |
|---|---|
| c | 12 |
| d | 13 |
| Internal Node | 14 |
| e | 16 |
| f | 45 |
Step3: Get two minimum frequency nodes by heap. New internal node added with frequency (12+13=25).
At this point min heap has 4 nodes where by 2 nodes usually are sources connected with single element each, and two heap nodes usually are root of tree along with more than one node.
| Character | Frequency |
|---|---|
| Internal Node | 14 |
| e | 16 |
| Internal Node | 25 |
| f | 45 |
Step4: Get two minimum frequency nodes. New internal node added with frequency (14+16=30).
Now min heap has 3 nodes.
| Character | Frequency |
|---|---|
| Internal Node | 25 |
| Internal Node | 30 |
| f | 45 |
Step5: get two minimum frequency nodes. New internal node added with frequency (25+30=55).
Now min heap has 2 nodes.
| Character | Frequency |
|---|---|
| f | 45 |
| Internal Node | 55 |
Step6: get two minimum frequency nodes. new internal node added with frequency (45+55=100).
Now min heap has only one node.
| Character | Frequency |
|---|---|
| Internal Node | 100 |
Since the heap has only one node, the algorithm stops here.
