Consider a binary max-heap implemented using an array. Which one of the…
2006
Consider a binary max-heap implemented using an array. Which one of the following arrays represents a binary max-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 159 students.
Show answer & explanation
Correct answer: C
Explanation:
A binary max-heap stored in an array requires each parent node to be greater than or equal to its children. Using 1-based indexing, for every parent at index i (1 ≤ i ≤ floor(n/2)), the following must hold: A[i] >= A[2i] and A[i] >= A[2i + 1] (if that child exists).
Check the candidate array 23, 17, 14, 7, 13, 10, 1, 5, 6, 12 by verifying each parent:
Index 1: 23 >= 17 and 14 — OK.
Index 2: 17 >= 7 and 13 — OK.
Index 3: 14 >= 10 and 1 — OK.
Index 4: 7 >= 5 and 6 — OK.
Index 5: 13 >= 12 (only left child exists) — OK.
Conclusion: The array 23, 17, 14, 7, 13, 10, 1, 5, 6, 12 satisfies the max-heap property and therefore represents a binary max-heap.
A video solution is available for this question — log in and enroll to watch it.