294 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]

__________________________________________________________________________

they are taking maximum level 11 and minimum level 2

__________________________________________________________________________

why minimum level 2, and why it is not 1?
+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

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.

0

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

+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

1
2