The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
354 views
A min heap having 1024 distinct elements with keys ranging from 0 to 1023 is stored in array of 1024 indices. The maximum difference between element 512 present at maximum level and minimum level is ________. [Assume root is present at level-1]

__________________________________________________________________________

Answer given 9

they are taking maximum level 11 and minimum level 2

__________________________________________________________________________

why minimum level 2, and why it is not 1?
asked in Programming by Veteran (109k points) | 354 views
+1
how 512 numbered element can be on level 1??

Because it is min heap, on the top of it (level 1), there will be only 1 element which will be the root of a tree and that element will be minimum among all the elements in heap
+1

why minimum level 2, and why it is not 1? Because at root only 0 will come since it is min heap, so 512 can be at  level-2 but not at level-1.

0
@akash @Anu

but how do u know 512th element is not the shortest element?
+1
question ask element 512 not 512th element.
+1
@Srestha

Yes, u are asking about 512 numbered element right!!!
0
yes , I got it

the elements in the array

0 to 1023

now 0 is root of heap

Now from 1 to 511 in left subtree and rest are in right subtree

right?
0
Can anyone please explain for maximum how it will be on 11th level? Shouldn't be the 512 present on 10th level if it will be on 11th level then no. of elements required will be 2048.
+1
11 because it started at 1
0
can any one please explain .......how to detect maximum level or minimum level in min heap.

Please explain how 9 is the answer.
+1

Total no. of levels with 1024 elements is 11.Its better if you try drawing the heap.


For 512 to be at level 2 (on left subtree) the heap will be like, 0,512,1,513,514,2,3,515,516,517,518,4,5,6,7…

Since from 0 to 1023 there are 1024 elements so the heap will have just one element at the last level. We try to make this element as 512.
I take a small example. For 16 elements 0 to 15, I need to make 8 come at the last level. This is how I can do that: 0,1,2,3,4,5,6,7,9,10,11,12,13,14,15,8.
Similarly in the heap with 1024 elements, the 2nd last level will contain 512 elements (29) and those will be 511,513,514…1023 and at the last level, the left child of 511 will be 512.
 

 

0
Thanks..
0

@MiNiPanda In the last line you mentioned " the left child of 511 2ill be 512"

Did you mean left child or the right child?

 

0

@,

Since this is a heap so all the nodes should be placed towards left as much as possible. So 512 will be the left child of 511. Not to be confused with BST. 

0
Yeah..exactly. Spot on :D

Thanks.
0

It could be helpful.

0
I understood answer I have very basic doubt

Given number , what is formulae to find it's level

I know this  is very basic , but I am struggling to find one for this example , assuming we haven't twisted graph

and drawn just in sequence 1,2,3,4,5,1023 in this increasing order only.

1 Answer

+1 vote
There are 1024 elements, there will be total 11 levels, 512 is the middle element. minimum level possible is Level 2 because 0 is the minimum element, Root should be 0, in the second level we can have 512.

 

Maximum level possible is Level 11.

 

Difference is 11-2 = 9
answered by Active (2.6k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
48,756 questions
52,850 answers
183,548 comments
68,742 users