GATE CS 2006 Q76 — Binary Heaps

In a $3$-ary heap represented by a $0$-indexed array $a$, the root is at index $0$. For any node at index $i$:

• Its children are located at indices: $3i + 1$, $3i + 2$, and $3i + 3$ (if they exist).

For an array of size $6$ (indices $0$ to $5$), the parent-child relationships are:

• The children of $a[0]$ are $a[1]$, $a[2]$, and $a[3]$.
• The children of $a[1]$ are $a[4]$ and $a[5]$.

For a max-heap, every parent node must be greater than or equal to its children. Thus, the following conditions must hold:

1. $a[0] \ge a[1]$, $a[0] \ge a[2]$, and $a[0] \ge a[3]$
2. $a[1] \ge a[4]$ and $a[1] \ge a[5]$

Let's evaluate the given options against these conditions:

• Option A: $[1, 3, 5, 6, 8, 9]$
  Here, $a[0] = 1$ and $a[1] = 3$. Since $1 < 3$, the max-heap property is violated.
• Option B: $[9, 6, 3, 1, 8, 5]$
  Here, $a[1] = 6$ and its child $a[4] = 8$. Since $6 < 8$, the max-heap property is violated.
• Option C: $[9, 3, 6, 8, 5, 1]$
  Here, $a[1] = 3$ and its child $a[4] = 5$. Since $3 < 5$, the max-heap property is violated.
• Option D: $[9, 5, 6, 8, 3, 1]$
  Let's verify all conditions:
  • $a[0] = 9 \ge \max(a[1], a[2], a[3]) = \max(5, 6, 8) = 8$ (True)
  • $a[1] = 5 \ge \max(a[4], a[5]) = \max(3, 1) = 3$ (True)
  All conditions are satisfied.