UGC NET CSE | October 2020 | Part 2 | Question: 24

Question

In a binary max heap containing $n$ numbers, the smallest element can be found in ______

• A. $O(n)$
• B. $O(\log _2 n)$
• C. $O(1)$
• D. $O(\log_2 \log_2 n)$

Answer 1

In binary max heaps, smallest element will be present at leaves which resides from $\lceil\frac{n}{2}\rceil$ to $n$ location so we need to traverse at max $\frac{n}{2}$ elements which takes O(n)$

GATE 2006

Hence Option A) is correct

Answer 2

https://www.geeksforgeeks.org/data-structures-and-algorithms-set-7/

Answer 3

In a max heap, the smallest element is always present at a leaf node. So we need to check for all leaf nodes for the minimum value. Worst case complexity will be O(n)