385 views
2 votes
2 votes
a min heap having 1024 distinct elements with keys ranging from 0 to 1023 is stored in an array of 1024 indices. the maximum difference between element 512 present at the maximum level and minimum level is            (assume root is present at level 1)

1 Answer

2 votes
2 votes

for clarity image https://drive.google.com/open?id=1f0JTn8EpIfpCw4NxpTKMhE6EwZVapQQO

(after analyzing the image with small sample )

there are 0-1023 elements ===> 1024 elements

when root is at height =1, then 1024 elements = ⌊ log 1024 ⌋ + 1 = 10 + 1 = 11 levels.

our main concern is on 512.

0,1,2,3 ...... 512, ....... 1022,1023

There are five hundred and twelve elements before 512 and five hundred eleven elements after it

 

is my 512 at level-11 ?

yes, due to there are atleast 10 elements less than it ! ===> yes it can be at level-11.

 

is my 512 at level-2 ?

if my 512 element is at level-2, then there should be atleast (29-1) - 1 i.e., 510 elements grater than 512.

in our range there are 511 elements grater than 512 ===> yes it can be at level-2.

 

∴ required answer = 11-2=9

No related questions found