GATE CS 2007 Q47 — Binary Heaps

To find the correct position for a newly inserted element in a Max Heap of size $n$ using binary search, we analyze the path from the new leaf to the root:

1. Path Length: A binary heap with $n$ elements has a height of $h = \lfloor \log_2 n \rfloor$. The path from any leaf to the root contains at most $h + 1$ nodes, which is $\Theta(\log_2 n)$ nodes.
2. Sorted Order: Due to the Max Heap property, the value of a parent node is always greater than or equal to its children. Thus, the elements along the path from the leaf to the root are sorted in non-decreasing order.
3. Binary Search: Since the path is sorted and its elements can be indexed directly (by repeatedly halving the array index), we can perform a binary search on this path of length $L = \Theta(\log_2 n)$ to find the insertion point.

The number of comparisons required for a binary search on a sorted sequence of length $L$ is $\Theta(\log_2 L)$.

Substituting $L = \Theta(\log_2 n)$:

Hence, the correct option is B.