Question

Let \(H\) be a binary min-heap consisting of \(n\) elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in \(H\)?

• A. \(\Theta(1)\)
• B. \(\Theta(\log n)\)
• C. \(\Theta(n)\)
• D. \(\Theta(n \log n)\)

Hint:

In a min-heap, only the minimum is efficiently accessible; finding the maximum requires scanning all leaves.

Answer 1

The Correct Option is C

Step 1: Understanding properties of a min-heap.
In a binary min-heap, the minimum element is always stored at the root. However, there is no ordering guarantee among sibling or leaf nodes with respect to the maximum element.

Step 2: Location of the maximum element.
The maximum element in a min-heap must be present among the leaf nodes. In the worst case, all leaf nodes must be examined to determine the maximum value.

Step 3: Time complexity analysis.
A binary heap with \(n\) elements has approximately \(\lceil n/2 \rceil\) leaf nodes. Scanning these nodes requires linear time. Hence, the worst case time complexity is \(\Theta(n)\).

Step 4: Conclusion.
Therefore, the correct answer is \(\Theta(n)\), corresponding to option (C).