in DS recategorized by
359 views
0 votes
0 votes
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)
in DS recategorized by
359 views

1 Answer

3 votes
3 votes

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

edited by

1 comment

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

2
2