In a binary max heap containing 𝑛 numbers, the smallest element can be found…
2020
In a binary max heap containing 𝑛 numbers, the smallest element can be found in ______
- A.
\(𝑂(𝑛) \) - B.
\( 𝑂(log_2𝑛) \) - C.
\(𝑂(1) \) - D.
\(𝑂(log_2log_2𝑛)\)
Attempted by 877 students.
Show answer & explanation
Correct answer: A
Key idea: In a max-heap every parent node is greater than or equal to its children, so the smallest element must be located at a leaf.
Location of leaves: In an array-based binary heap the leaf nodes occupy the indices floor(n/2) + 1 through n, which is about n/2 elements.
Search method: Scan all leaf nodes and keep the minimum seen. Since there are Θ(n) leaves, this scan takes Θ(n) time.
Conclusion: The smallest element can be found in O(n) time (more precisely Θ(n)) in a binary max-heap.
Note: If the data structure is augmented to maintain the minimum as elements are inserted and deleted, retrieval can be O(1), but that requires extra bookkeeping beyond a plain max-heap.
A video solution is available for this question — log in and enroll to watch it.