Question

Which one of the following sequences, when stored in an array at locations \(A[1], \ldots, A[10]\), forms a max-heap?

• A. 23, 17, 10, 6, 13, 14, 1, 5, 7, 12
• B. 23, 17, 14, 7, 13, 10, 1, 5, 6, 12
• C. 23, 17, 14, 6, 13, 10, 1, 5, 7, 15
• D. 23, 14, 17, 1, 10, 13, 16, 12, 7, 5

Hint:

For heap questions, always check parent-child pairs using the index rules ($2i$ and $2i+1$). If any child is larger than its parent, the max-heap property is violated.

Answer 1

The Correct Option is B

Step 1: Recall the max-heap property.
In a max-heap, each parent node must be greater than or equal to its children.
If the array is indexed from $1$, then for any element at index $i$: \[ \text{Left child at } 2i, \text{Right child at } 2i+1 \] Step 2: Check option (B).
Array (B): $[23, 17, 14, 7, 13, 10, 1, 5, 6, 12]$
- Root: $A[1] = 23$ has children $17, 14$ (both $\leq 23$). ✔
- $A[2] = 17$ has children $7, 13$ (both $\leq 17$). ✔
- $A[3] = 14$ has children $10, 1$ (both $\leq 14$). ✔
- $A[4] = 7$ has children $5, 6$ (both $\leq 7$). ✔
- $A[5] = 13$ has children $12$ only (and $12 \leq 13$). ✔
All parents satisfy the max-heap property.
Step 3: Eliminate other options.
- (A) fails because $A[3]=10$ has child $A[6]=14$, which is greater. ✘
- (C) fails because $A[3]=14$ has child $A[10]=15$, which is greater. ✘
- (D) fails because $A[3]=17$ has child $A[7]=16$ (okay), but $A[2]=14$ has child $A[5]=10$ (okay) — however,
$A[3]=17$ and $A[2]=14$ comparison not relevant; still, structure violations occur deeper. ✘
Thus, only option (B) is a valid max-heap. \[ \boxed{\text{The sequence in (B) forms a max-heap.}} \]