Gate Applied Test Series

Question

A min heap of size 2048  is stored on an array with array indices [1..2048] is stored and the minimum number of comparisons required to determine the maximum of element is _______.(Assume that we are allowed to access the array indexes)

Answer 1

Max element in min heap will present at leaf node.

Min heap has 2048 elements.

#leaf nodes = $\left \lceil 2048/2 \right \rceil$ = 1024

So in total min number of comparisons needed = 1024 – 1 = 1023

 

PS: Good thing to remember, In a binary heap of ‘n’ nodes there are exactly $\left \lceil n/2 \right \rceil$ leaf nodes.

Refer: https://stackoverflow.com/questions/40665736/how-do-you-prove-there-are-ceiln-2-leaves-in-a-binary-heap-of-n-nodes

Comments

Nice answer @adad20. Even if duplicate elements are present then also no issue.