As far as I know, a minheap is data structure whose parent node's value is less than child node and maxheap is when parent node is greater than child node. Here they have used minheap. But as the node closer to root have less length code than nodes below that level i.e., level 1 codes will have shorter codes than level 5; which means level 1 nodes are more frequently occurring than level 5 nodes. Also the numeric value after addition is also greater than that nodes at high level. I am confused, isn't that definition of max heap but they are using min heap. Please explain why they are using Min heap and not Max heap (considering nodes at lower level are more frequent than at higher level)
Building a Huffman tree is bottom up.
You start with the all the leaf nodes with their frequency.
Then you select and remove the 2 nodes with the smallest frequencies
create and insert a new compound node with the 2 selected nodes and it's new frequency is the sum of the 2 nodes
if set has 2 or more nodes repeat from step 2
Selecting the 2 nodes with the least frequencies requires a min heap.
Actually the more efficient algorithm (described by Moffat in 1995 or so) is the following:
- sort input nodes by frequency, put them into queue A
- make an empty queue B for intermediate nodes
- choose two smallest nodes among two smallest nodes in A and two smallest nodes in B, and pull them off their queues
- push combined node into the queue B
- repeat until you have no nodes in A and only one node in B
This way, nodes in A and B remains sorted, so you can find smallest ones on the end of queue.
As result, after initial sort (which is usually count sorting with #buckets ~= #nodes, plus something simple for a few remaining too large elements), you access both queues only sequentially, so the algorithm spends only ~10 cpu cycles per node.
AFAIR, Moffat idea was even more advanced, allowing to build huffman tree in-place for a small runtime penalty compared to the standard queue implementation.