GATE CS 2003 Q23 — Binary Heaps

In a min-heap, the smallest element is always at the root (level 0). The second smallest element must be one of the children of the root (level 1).

More generally, the $k^{\text{th}}$ smallest element in a min-heap must reside within the first $k$ levels of the heap. This is because any path from the root to a node is in non-decreasing order, so an element cannot be smaller than its ancestors.

For $k = 7$:

• The $7^{\text{th}}$ smallest element must be located within the top $7$ levels of the min-heap.
• The maximum number of nodes in the first $7$ levels of a binary tree is $2^7 - 1 = 127$.
• Since $127$ is a constant that does not depend on the total number of elements $n$, we only need to search a constant number of elements to find the $7^{\text{th}}$ smallest element.

Therefore, the time complexity to find the $7^{\text{th}}$ smallest element is $\Theta(1)$.