Question 12

In a binary min-heap, the value at any node is less than or equal to the values of its children. By induction, the maximum element cannot be an internal node that has children, because each child would be greater than or equal to it.

Therefore, the maximum element must be located at one of the leaf nodes.

In an $n$-element binary heap represented as an array, the leaves occupy indices from $\lfloor n/2 \rfloor + 1$ to $n$. The number of leaves is $\lceil n/2 \rceil = \Theta(n)$.

The leaf elements are not stored in sorted order. Finding the maximum among them requires scanning all $\Theta(n)$ leaves. Thus, the worst-case time complexity of an optimal algorithm to find the maximum is $\Theta(n)$.