GATE CS 2015 Set 1 Q.42 (CS Q.32): Binary Heaps and Priority Queues

Consider a max heap, represented by the array:

Array Index	1	2	3	4	5	6	7	8	9
Value	40	30	20	10	15	16	17	8	4

Now consider that a value $35$ is inserted into this heap. After insertion, the new heap is:

$40, 30, 20, 10, 15, 16, 17, 8, 4, 35$

$40, 35, 20, 10, 30, 16, 17, 8, 4, 15$

$40, 30, 20, 10, 35, 16, 17, 8, 4, 15$

$40, 35, 20, 10, 15, 16, 17, 8, 4, 30$

Official answer and solution

Solution

Simulate standard binary max-heap insertion at the end of the array followed by heapify-up (bubble-up).

The initial 1-indexed heap array is:

A = [40, 30, 20, 10, 15, 16, 17, 8, 4]

with size $n = 9$ .

Append the new element $35$ at index $10$ :
$A[10] = 35.$
Compare $A[10]$ with its parent at $\lfloor 10/2 \rfloor = 5$ ( $A[5] = 15$ ):
Since $35 > 15$ , swap $A[10]$ and $A[5]$ :
$A = [40, 30, 20, 10, \mathbf{35}, 16, 17, 8, 4, \mathbf{15}].$
Compare new $A[5] = 35$ with its parent at $\lfloor 5/2 \rfloor = 2$ ( $A[2] = 30$ ):
Since $35 > 30$ , swap $A[5]$ and $A[2]$ :
$A = [40, \mathbf{35}, 20, 10, \mathbf{30}, 16, 17, 8, 4, 15].$
Compare new $A[2] = 35$ with its parent at $\lfloor 2/2 \rfloor = 1$ ( $A[1] = 40$ ):
Since $40 > 35$ , the max-heap property is satisfied and insertion terminates.

The resulting array is:

40, 35, 20, 10, 30, 16, 17, 8, 4, 15.

This matches option B.

Final answer

Common trap

Stopping bubble-up after only one swap, failing to compare with the grandparent node at index 2.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.