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?
Answer
(D)
Explanation
No option starts with the smallest key, 11, so the heap meant is a max-heap. Build it bottom-up, sifting down from the last internal node (position 5) back to the root:
- 111 is already larger than its child 93; 11 swaps with its larger child 131; 90 stays above 75 and 33.
- 101 swaps with its larger child, now 131.
- At the root, 82 swaps with 131, then with 111, then with 93.
The heap is [131, 111, 90, 101, 93, 75, 33, 11, 44, 82], and inserting the keys one at a time gives the same first three. Option C is impossible because 11, the smallest key, cannot have children in a max-heap; A and B do not start with the maximum, 131.
Answer: D