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

is it 1013 ?

---

Answer given is 1014.

Could you please explaint the approach?

---

^it is a 10 level min heap root at 0
there will n/2 internal nodes nd n/2 leaf nodes
at n/2 ie last internal node with value 9 bcoz it is at 9th level
so max diff =1023-9=1014

---

.......................

---

In that case, answer will be 1023 - 10 = 1013

height =  $\left \lfloor \log 1024 \right \rfloor = 10$

n/2 will be the last non-leaf node

so the maximum value we can place in it will be 1023 and minimum value will be 10.

---

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

---

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.

---

@akash @Anu

but how do u know 512th element is not the shortest element?

---

question ask element 512 not 512th element.

---

@Srestha

Yes, u are asking about 512 numbered element right!!!

---

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?

---

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.

---

11 because it started at 1

---

can any one please explain .......how to detect maximum level or minimum level in min heap.

Please explain how 9 is the answer.

---

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 (2⁹) and those will be 511,513,514…1023 and at the last level, the left child of 511 will be 512.
 

 

---

Thanks..

---

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

Did you mean left child or the right child?

 

---

@`JEET,

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. 

---

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