Which of the following sequences of array elements forms a heap?
2006
Which of the following sequences of array elements forms a heap?
- A.
{23, 17, 14, 6, 13, 10, 1, 12, 7, 5}
- B.
{23, 17, 14, 6, 13, 10, 1, 5, 7, 12}
- C.
{23, 17, 14, 7, 13, 10, 1, 5, 6, 12}
- D.
{23, 17, 14, 7, 13, 10, 1, 12, 5, 7}
Attempted by 216 students.
Show answer & explanation
Correct answer: C
Key idea: For a max-heap stored in an array (0-based), each parent at index i must be greater than or equal to its children at indices 2i+1 and 2i+2.
Check the candidate array {23, 17, 14, 7, 13, 10, 1, 5, 6, 12}:
Index 0: parent = 23, children = 17 and 14 → 23 >= 17 and 23 >= 14 (OK).
Index 1: parent = 17, children = 7 and 13 → 17 >= 7 and 17 >= 13 (OK).
Index 2: parent = 14, children = 10 and 1 → 14 >= 10 and 14 >= 1 (OK).
Index 3: parent = 7, children = 5 and 6 → 7 >= 5 and 7 >= 6 (OK).
Index 4: parent = 13, child = 12 (only left child for this index) → 13 >= 12 (OK).
Because every parent is greater than or equal to its children, the array satisfies the max-heap property and is therefore a valid heap.
Conclusion: The sequence {23, 17, 14, 7, 13, 10, 1, 5, 6, 12} is a valid max-heap.