GATE CS 2016 Set 2 Q34 — Binary Heaps

To find the maximum depth at which the integer $9$ can appear in the min-heap, let us analyze the properties of a min-heap and the structure of the tree.

1. Tree Structure and Depths

The heap contains $N = 1023$ nodes. Since it is a complete binary tree, the depths of the nodes range from $0$ (the root) to $\log_2(1023+1) - 1 = 9$.

2. Min-Heap Property along a Path

In a min-heap, the value of any node is strictly less than the values of its children. Therefore, if we trace a path from the root to any node at depth $d$, the values of the nodes along this path must be strictly increasing.

Let the path from the root to the node containing the integer $9$ at depth $d$ be:

where $v_0$ is the root (depth $0$) and $v_d$ is the node containing $9$ (depth $d$). Due to the min-heap property:

3. Finding the Maximum Depth $d$

Since the heap contains distinct integers from the range $[1, 1023]$, the smallest possible integers we can assign to the nodes along this path to minimize the value at depth $d$ are the smallest available positive integers:

• $\text{val}(v_0) \ge 1$
• $\text{val}(v_1) \ge 2$
• $\text{val}(v_2) \ge 3$
• $\dots$
• $\text{val}(v_d) \ge d + 1$

Since the node at depth $d$ contains the integer $9$, we have:

4. Feasibility of Depth 8

We can easily construct such a heap where the path from the root to depth $8$ is $1 \to 2 \to 3 \to 4 \to 5 \to 6 \to 7 \to 8 \to 9$. The remaining $1014$ nodes in the tree can be filled with the remaining integers from $[10, 1023]$ without violating the min-heap property, as all remaining elements are strictly greater than $9$.

Thus, the maximum depth at which the integer $9$ can appear is 8.