GATE CS 2006 Q77 — Binary Heaps

In a $3$-ary heap represented by a $0$-indexed array, the parent of a node at index $i$ is located at index $\lfloor (i-1)/3 \rfloor$.

From the previous question (Q.76), the valid $3$-ary max heap is represented by the array:
$a = [9, 5, 6, 8, 3, 1]$

We insert the elements $7, 2, 10,$ and $4$ one by one:

1. Insert $7$:
   • Place $7$ at the end: $[9, 5, 6, 8, 3, 1, \mathbf{7}]$. Here, $7$ is at index $6$.
   • Its parent is at index $\lfloor (6-1)/3 \rfloor = 1$, which has value $5$.
   • Since $7 > 5$, swap them: $[9, \mathbf{7}, 6, 8, 3, 1, \mathbf{5}]$.
   • The parent of index $1$ is index $0$ (value $9$). Since $9 \ge 7$, heap property is satisfied.
2. Insert $2$:
   • Place $2$ at the end: $[9, 7, 6, 8, 3, 1, 5, \mathbf{2}]$. Here, $2$ is at index $7$.
   • Its parent is at index $\lfloor (7-1)/3 \rfloor = 2$ (value $6$). Since $2 \le 6$, no swap is needed.
3. Insert $10$:
   • Place $10$ at the end: $[9, 7, 6, 8, 3, 1, 5, 2, \mathbf{10}]$. Here, $10$ is at index $8$.
   • Its parent is at index $\lfloor (8-1)/3 \rfloor = 2$ (value $6$). Since $10 > 6$, swap them: $[9, 7, \mathbf{10}, 8, 3, 1, 5, 2, \mathbf{6}]$.
   • Now, the parent of index $2$ is index $0$ (value $9$). Since $10 > 9$, swap them: $[\mathbf{10}, 7, \mathbf{9}, 8, 3, 1, 5, 2, 6]$.
4. Insert $4$:
   • Place $4$ at the end: $[10, 7, 9, 8, 3, 1, 5, 2, 6, \mathbf{4}]$. Here, $4$ is at index $9$.
   • Its parent is at index $\lfloor (9-1)/3 \rfloor = 2$ (value $9$). Since $4 \le 9$, no swap is needed.

The final array representation is: $[10, 7, 9, 8, 3, 1, 5, 2, 6, 4]$, which matches Option A.