GATE CSE
First time here? Checkout the FAQ!
x
+10 votes
1.2k views
A complete binary min-heap is made by including each integer in $[1, 1023]$ exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth $0$. The maximum depth at which integer $9$ can appear is _________.
asked in DS by Veteran (40.8k points)  
edited by | 1.2k views
if they ask  maximum no of nodes till the level where integer 9 has been occured then answer will be 511

4 Answers

+20 votes
Best answer

Here answer is 8. With 1024 nodes, we can easily build min heap Check following diagram

Now once we place 1-9 then remaining elements can be placed easily to fill up heap (While keeping heap property of course) Total elements we need for this heap is 512, we have given 1024 ! So Yes, 8 is answer !

answered by Veteran (40.8k points)  
selected by
How can you call this a heap ? Heap is an almost complete binary tree . Is this almost complete ? No.

yes ...heap should be a complete binary tree and here also it is  a complete BT. Because we have total 1024 elements and with height(or depth) = 9 we can have total (2(9+1) - 1) = 1023 element in complete BT.

Actually we need 511 elements for this heap. The max. depth possible is 8, so max. nodes that can be present in a complete binary tree of depth 8 = 511.

But since we have 1023 elements, we could achieve a complete binary min. heap of depth 9, which would cover all 1023 elements. But, the max. depth of node 9 can only be 8. Actually max. depth of node 10 can be 9 but that is not asked here.
The kth smallest element cannot be deeper than the kth level of the heap, since the path from it to the root must go through elements of decreasing value. (root is at level 1)

9 is 9th smallest.
So, 9 can be at level 9 i.e. at depth 8.
+8 votes
Add 1,2,3,4,5,6,7,8,9 in left skewed fashion. Remaining elements can be added accordingly. So, 9 will be present at depth 8.
answered by Active (1.4k points)  
Answer is correct , explanation is wrong.
I am getting 3. Because it's complete min binary heap. I don't know how they are getting 8.
Navin , check my answer, you'll know !
how the ans is 8 ?pls explain? yes it will be 8 if the tree is not complete ?if it is complete then each parent node will have left child and right child.Then how the tree will look like?

 babai  in image akash just put imagination of tree .. in his ans right of root node i.e. 1 there are 255 nodes in arragment which satisfies the given condition... like then right of node 2 there are 127 nodes... like this tree will be look like...

yess but i can't understand how 255 nodes are there in the right of root node and this satisfying this condition  pls explain this Anirudh once this clear rest will be easy.
check with 8 nodes ,, put 1,2,3 on left side rest full with property of min heap.( root should be less than left or right child , their is no comparision between left and right child)

he done right on top of his explaination...try to do for 16 nodes.

you get idea..
yes now clear thanks
+4 votes
In minheap

ParentNode <= ChildNode

So if ChildNode = 9 then parent can be from [1,8]...choose 8 since we max depth

So if ChildNode = 8 then parent can be from [1,7]...choose 7 since we max depth

...

...

So if ChildNode = 2 then parent will be 1

so total depth will be 8
answered by Active (1.6k points)  
0 votes
With 1023 elements the min height of a tree can be = floor(log1023) i.e 9.

here Depth and height have direct correlation max depth possible=max height

we can construct a tree such that all integers below 9 fall on one side and can preserve max-heap property as well.

now how many elements which are less than 9 are there so that you can construct such tree?

Integers less than 9 are 8. so at every level we use one integer to place 9 as far as possible from root so that we can get max depth.

so 8 such integers are there hence answer is 8.

Had they given something like this [0,1023] then max depth =9.

I know this answer requires lot of intuition , im sorry if this is not clear.
answered by (79 points)  
Top Users Jan 2017
  1. Debashish Deka

    9716 Points

  2. sudsho

    5560 Points

  3. Bikram

    5290 Points

  4. Habibkhan

    4910 Points

  5. Vijay Thakur

    4498 Points

  6. Arjun

    4418 Points

  7. saurabh rai

    4236 Points

  8. Sushant Gokhale

    4226 Points

  9. Kapil

    3848 Points

  10. santhoshdevulapally

    3808 Points

Monthly Topper: Rs. 500 gift card

19,449 questions
24,228 answers
53,954 comments
20,373 users