0
$\begingroup$

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)

$\endgroup$

3 Answers 3

3
$\begingroup$

Building a Huffman tree is bottom up.

  1. You start with the all the leaf nodes with their frequency.

  2. Then you select and remove the 2 nodes with the smallest frequencies

  3. create and insert a new compound node with the 2 selected nodes and it's new frequency is the sum of the 2 nodes

  4. if set has 2 or more nodes repeat from step 2

Selecting the 2 nodes with the least frequencies requires a min heap.

$\endgroup$
2
  • $\begingroup$ @freak are u saying the direction from which heap are constructed determines their min/max type? or is it just for huffman tree $\endgroup$
    – pebble
    Nov 8, 2017 at 14:50
  • 1
    $\begingroup$ @pebble no the only operation you do on the set of nodes is see if it's empty, get and remove the smallest element and add new element. Those are exactly the operations a min heap supports $\endgroup$ Nov 8, 2017 at 14:58
1
$\begingroup$

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.

$\endgroup$
-2
$\begingroup$

ih huffman code,not nodes value should be considered.Only codes assigned should be considered.If u consider the code,only the upper level nodes will have least bit code

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.