GATE CS 2015 Set 1 Q32 — Binary Heaps

To insert a value into a max-heap, we follow a two-step process:

1. Insert the new element at the next available position in the complete binary tree (at the end of the array).
2. Perform a heapify-up (or bubble-up) operation to restore the max-heap property.

Step-by-Step Execution:

1. Initial Array (1-indexed):

$$\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 40 & 30 & 20 & 10 & 15 & 16 & 17 & 8 & 4 \\ \hline \end{array}$$

2. Insert $35$ at index 10:

$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline 40 & 30 & 20 & 10 & 15 & 16 & 17 & 8 & 4 & \mathbf{35} \\ \hline \end{array}$$

3. Heapify-up from index 10:

• The parent of index $10$ is index $\lfloor 10/2 \rfloor = 5$ (value $15$).
• Since $35 > 15$, we swap them:

$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline 40 & 30 & 20 & 10 & \mathbf{35} & 16 & 17 & 8 & 4 & \mathbf{15} \\ \hline \end{array}$$

• The parent of index $5$ is index $\lfloor 5/2 \rfloor = 2$ (value $30$).
• Since $35 > 30$, we swap them:

$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline 40 & \mathbf{35} & 20 & 10 & \mathbf{30} & 16 & 17 & 8 & 4 & 15 \\ \hline \end{array}$$

• The parent of index $2$ is index $\lfloor 2/2 \rfloor = 1$ (value $40$).
• Since $35 \le 40$, the max-heap property is satisfied. The process terminates.

The final array representation of the max-heap is:
$40, 35, 20, 10, 30, 16, 17, 8, 4, 15$

Thus, the correct option is B.