in Algorithms edited by
220 views
3 votes
3 votes

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

  1. $O(n)$
  2. $O(\log n)$
  3. $O(n \log n)$ but not $O(n)$
  4. $O(1)$
in Algorithms edited by
by
220 views

1 Answer

4 votes
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

edited by

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

0
0
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))
0
0
Answer:

Related questions