Gate2020 cs Q50

50Consider the array representation of a binary min-heap containing 1023 element. The minimum number of comparisons required to find the maximum in the heap is ______.

Note – Numerical Type question

Option : A
Explanation :
Min-heap contains 1023 elements.
Min-heap means, parent should be minimum or equal to it’s children so, max children could be either left or right one.
Following this logic, maximum can be definitely at leaf nodes.

No. of elements in leaf = n/2 = 1023/2 = 512
To find maximum among 512 elements, no. of comparisons needed is 511.

Forgot your password?

I agree with the Terms.