GATE CS 2009 Q59 — Binary Heaps

In an array-based representation of a binary heap (using 1-based indexing), a node at index $i$ has its left child at index $2i$ and its right child at index $2i + 1$.

For a max-heap, the value of a parent node must be greater than or equal to the values of its children: $A[i] \ge A[2i]$ and $A[i] \ge A[2i+1]$.

Let us evaluate the options:

• Option A: $\{25, 12, 16, 13, 10, 8, 14\}$
  At index $2$, the parent is $12$. Its left child at index $4$ is $13$. Since $12 < 13$, this violates the max-heap property.
• Option B: $\{25, 14, 13, 16, 10, 8, 12\}$
  At index $2$, the parent is $14$. Its left child at index $4$ is $16$. Since $14 < 16$, this violates the max-heap property.
• Option C: $\{25, 14, 16, 13, 10, 8, 12\}$
  Let's check all parent-child relations:
  • Index $1$ ($25$) $\ge$ Index $2$ ($14$) and Index $3$ ($16$)   (True)
  • Index $2$ ($14$) $\ge$ Index $4$ ($13$) and Index $5$ ($10$)   (True)
  • Index $3$ ($16$) $\ge$ Index $6$ ($8$) and Index $7$ ($12$)   (True)
  All conditions are satisfied. Thus, this represents a valid max-heap.
• Option D: $\{25, 14, 12, 13, 10, 8, 16\}$
  At index $3$, the parent is $12$. Its right child at index $7$ is $16$. Since $12 < 16$, this violates the max-heap property.