GATE CS 2011 Q23 — Binary Heaps

A max-heap must satisfy two essential properties:

1. Shape Property (Complete Binary Tree): All levels of the tree must be completely filled, except possibly the last level, which must be filled from left to right.
2. Max-Heap Property: For every node $i$ (except the root), the value of the parent of $i$ must be greater than or equal to the value of $i$ ($\text{parent}(i) \ge \text{node}(i)$).

Let us evaluate each option based on these properties:

• Option A: Violates the max-heap property because the root node with value $10$ has a right child with value $12$ (since $12 > 10$, the parent is smaller than its child).
• Option B:

  The tree structure is:

            10
           /  \
          8    5
         / \  /
        7   6 4
      

  • It is a complete binary tree because all levels are filled from left to right.
  • It satisfies the max-heap property at every node:
    • $10 \ge 8$ and $10 \ge 5$
    • $8 \ge 7$ and $8 \ge 6$
    • $5 \ge 4$
  Thus, this is a valid max-heap.
• Option C: Violates the complete binary tree property because the node $5$ has a right child $4$ but no left child. The last level is not filled from left to right.
• Option D: Violates the max-heap property because the node $5$ has a right child $11$, and $11 > 5$.