GATE CS 2023 Q2 — Binary Heaps

For an array $A[1 \ldots N]$ to represent a max-heap, the parent-child relationship must satisfy the max-heap property: for every element at index $i$ (where $2 \le i \le N$), its parent at index $\lfloor i/2 \rfloor$ must be greater than or equal to it. That is:

Let's verify the options:

• Option A: $A = [23, 17, 10, 6, 13, 14, 1, 5, 7, 12]$. For $i = 6$, the child is $A[6] = 14$ and its parent is $A[3] = 10$. Since $14 > 10$, this violates the max-heap property.
• Option B: $A = [23, 17, 14, 7, 13, 10, 1, 5, 6, 12]$. Let's check all parent-child relations:
  • Children of $A[1]=23$ are $A[2]=17$ and $A[3]=14$ (Valid: $23 \ge 17, 14$)
  • Children of $A[2]=17$ are $A[4]=7$ and $A[5]=13$ (Valid: $17 \ge 7, 13$)
  • Children of $A[3]=14$ are $A[6]=10$ and $A[7]=1$ (Valid: $14 \ge 10, 1$)
  • Children of $A[4]=7$ are $A[8]=5$ and $A[9]=6$ (Valid: $7 \ge 5, 6$)
  • Child of $A[5]=13$ is $A[10]=12$ (Valid: $13 \ge 12$)
  All conditions are satisfied. This is a valid max-heap.
• Option C: $A = [23, 17, 14, 6, 13, 10, 1, 5, 7, 15]$. For $i = 10$, the child is $A[10] = 15$ and its parent is $A[5] = 13$. Since $15 > 13$, this violates the max-heap property.
• Option D: $A = [23, 14, 17, 1, 10, 13, 16, 12, 7, 5]$. For $i = 8$, the child is $A[8] = 12$ and its parent is $A[4] = 1$. Since $12 > 1$, this violates the max-heap property.