"Since we cannot be sure of the minimum no. of elements in leaf we can only use *O* and not Θ" I am not getting this sentence can you please explian in detail.

Dark Mode

218 views

4 votes

Best answer

Maximum element in a min-heap can be found only at the leaf. Total number of leaf nodes in a binary heap is exactly $\lceil \frac{n}{2}\rceil$ and there is no ordering among these elements and so we need $\lceil \frac{n}{2}\rceil$ comparisons to find the maximum. Being represented in an array, we can index to all leaf nodes in constant time. Hence, our required answer is $\Theta (n)$ which also implies $O(n).$

Correct option A.

Ref: https://cs.stackexchange.com/questions/841/proving-a-binary-heap-has-lceil-n-2-rceil-leaves

0