An array [82, 101, 90, 11, 111, 75, 33, 131, 44, 93] is heapified. Which one…
2024
An array [82, 101, 90, 11, 111, 75, 33, 131, 44, 93] is heapified. Which one of the following options represents the first three elements in the heapified array?
- A.
82, 90, 101
- B.
82, 11, 93
- C.
131, 11, 93
- D.
131, 111, 90
Attempted by 234 students.
Show answer & explanation
Correct answer: D
Key insight: build a max-heap (largest element becomes the root) using the standard bottom-up heapify.
Start with the array: [82, 101, 90, 11, 111, 75, 33, 131, 44, 93].
Heapify index 3: swap 11 and 131 → [82, 101, 90, 131, 111, 75, 33, 11, 44, 93].
Heapify index 1: swap 101 and 131 → [82, 131, 90, 101, 111, 75, 33, 11, 44, 93].
Heapify index 0: swap 82 and 131 → [131, 82, 90, 101, 111, 75, 33, 11, 44, 93]. Then fix index 1 by swapping 82 and 111 → [131, 111, 90, 101, 82, 75, 33, 11, 44, 93], and finally swap 82 and 93 → [131, 111, 90, 101, 93, 75, 33, 11, 44, 82].
Final heapified array: [131, 111, 90, 101, 93, 75, 33, 11, 44, 82]. The first three elements are 131, 111, 90.
A video solution is available for this question — log in and enroll to watch it.