Min heap

Question

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 the keys of all the element that can possibly be stored at (n/2)th index of the array is...........

Comments

Yeah..exactly. Spot on :D

Thanks.

---

It could be helpful.

---

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.

Answer 1

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

Answer 2

since there are 1024 elements, there will be ceil{log(1+1024)}=11 levels, so in worst case, the 512 can be present at level 11(last level)

in best case the element  512 can be present only at level 2, it root is at level 1

then the difference = 11-2=9

Answer is 9