CODEWITHSUNDEEP
data-structuresheap
give_it_a_bit
give_it_a_bit

Reputation: 189

Maximum depth of a min heap

Consider a min heap containing all the integers from 1 to 1023 exactly once. If root is at depth 0, the maximum depth at which 9 can appear is? The answer to the question is 8.

But, considering that a min heap is a nearly complete BT with-

1) for d <- 0 to h-1, all levels have 2^d nodes.

2) for d <- h, nodes are filled from left.

Source:http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/nearly_complete.pdf

What mistake is in answer being 4,as the level order traversal would be {1,2 3,4 5 6,7 8 9...}

Upvotes: 1

Views: 707

Answers (1)

give_it_a_bit
give_it_a_bit

Reputation: 189

The min-heap requires to put elements which are greater than their parent node.

Considering the question, one can put 1 as root, then 2 as its left child and any element greater than 9 (say 512) as its right child.For 2, one can continue in this way by putting 3 as left child and, say 513 as its right child. The final min heap obtained will be -

                   1
                  / \
                 /   \
                2     512
               / \      /\
              /   \    /  \
             3   513  514  515
            /\    /\   /\   /\
           /  \  
          4  516  .  .  .  .  .  . 
         /   / \ /\  /\ /\ /\ /\ /\
        5   .  . ..  .. .. .. .. ...
       /   /\ /\ /\/\
      6   . . . . ........................... 
     /
    7 .......................................................
   /   
  8 ......................................................
 /
9

The dots denote filled levels and can be replaced by elements from [517,758], as the levels must be filled.

The depth of 9 is 8

Upvotes: 1

Related Questions