Steps to build Huffman Tree
1. Create a leaf node for each unique character and build a min heap of all leaf nodes (Min Heap is used as a priority queue. The value of frequency field is used to compare two nodes in min heap. Initially, the least frequent character is at root)
2. Extract two nodes with the minimum frequency from the min heap.
3. Create a new internal node with the frequency equal to the sum of the two nodes frequencies. Make the first extracted node as its left child and the other extracted node as its right child. Add this node to the min heap.
4. Repeat steps#2 and #3 until the heap contains only one node. The remaining node is the root node and the tree is complete.
Character |
Frequency |
p |
7 |
q |
9 |
r |
5 |
s |
5 |
Extract two minimum frequency nodes . Add a new internal node with frequency 5 + 5 = 10.
character |
frequency |
p |
7 |
q |
9 |
rs |
10 |
Extract two minimum frequency nodes . Add a new internal node with frequency 7 + 9 = 16.
character |
frequency |
pq |
16 |
rs |
10 |
Character |
bits |
p |
10(2 bits) |
q |
11 ( 2 bits) |
r |
00 ( 2 bits ) |
s |
01 ( 2 bits ) |
The number of bits required for Huffman encoding: $( 7 + 9 + 5 + 5 ) * 2 = 52 \ bits$