GATE CS 2006 Q10 — Binary Heaps

In a binary max-heap of size $n$, the properties of the heap structure dictate where elements are located:

• The largest element is always at the root (index $1$ in an array representation).
• The smallest element must be one of the leaf nodes, as any path from the root to a leaf is non-increasing.

In a complete binary tree with $n$ elements, the leaf nodes are located at indices from $\lfloor n/2 \rfloor + 1$ to $n$. The number of leaf nodes is $\lceil n/2 \rceil$, which is $O(n)$.

Since the leaf nodes are not maintained in any sorted order relative to each other, we must perform a linear search across all the leaf nodes to find the minimum element. This search requires checking $\lceil n/2 \rceil$ elements, which takes $\Theta(n)$ time in the worst case.

Therefore, the smallest element can be found in $O(n)$ time.