GATE Overflow | Algorithms | Test 1 | Question: 26

Question

Maximum element in a min-heap represented by an array, can be computed in _____  time

• A. $O(n)$
• B. $O(\log n)$
• C. $O(n \log n)$ but not $O(n)$
• D. $O(1)$

Answer 1

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

Comments

"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.

---

for finding Max element in min heap , we can heapify heap to max heap in Log(n) , and first element will be max element.
So According to my concept it should be of O(log(n))