GATE CS 2021 Set 2 Q2 — Binary Heaps

In a binary min-heap of size $n$, the elements satisfy the min-heap property where the key of each node is less than or equal to the keys of its children. Consequently:

• The minimum element is always located at the root node (index $0$ or $1$ in the array representation).
• The maximum element cannot have any children, meaning it must be located at one of the leaf nodes.

For a complete binary tree with $n$ elements, the leaf nodes are located in the second half of the array, specifically from index $\lfloor n/2 \rfloor$ to $n-1$ (using 0-based indexing). The number of leaf nodes is $\lceil n/2 \rceil$.

Since there is no relative ordering or heap property maintained among the leaf nodes themselves, finding the maximum element requires a linear scan over all the leaf nodes.

The time complexity to find the maximum among the $\lceil n/2 \rceil$ unsorted leaf elements is:

Therefore, the worst-case time complexity of an optimal algorithm to find the maximum element in a binary min-heap is $\Theta(n)$.