The array below is turned into a min-heap in place by the standard bottom-up build-heap procedure: for down to , sift down, at each step swapping it with its smaller child as long as that child is smaller than it. The children of are and .
| Index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| Value | 45 | 12 | 78 | 33 | 9 | 60 | 21 | 5 | 40 | 18 |
Which one of the following is the array after build-heap finishes?
Show solution
Solution MCQ · 2 marks · −⅔ if wrong
Answer: (A) 5, 9, 21, 12, 18, 60, 78, 33, 40, 45
Method: trace the sift-downs from the last internal node to the root.
, so start at .
- : , child . No swap.
- : , children 5 and 40. Swap with 5. Array: 45, 12, 78, 5, 9, 60, 21, 33, 40, 18.
- : , children 60 and 21. Swap with 21. Array: 45, 12, 21, 5, 9, 60, 78, 33, 40, 18.
- : , children 5 and 9. Swap with 5; at index 4, 12 has children 33 and 40, stop. Array: 45, 5, 21, 12, 9, 60, 78, 33, 40, 18.
- : , children 5 and 21. Swap with 5. At index 2, children 12 and 9: swap with 9. At index 5, child 18: swap. Array: 5, 9, 21, 12, 18, 60, 78, 33, 40, 45.
Final: 5, 9, 21, 12, 18, 60, 78, 33, 40, 45 (6 swaps in all).
Trap. Options (b) and (d) are also valid min-heaps. A question about a procedure is answered by tracing that procedure, not by checking the heap property. Inserting keys one at a time builds a different heap from the same keys. And a sift-down continues until the key is no larger than both children, which can take it several levels (45 travels from index 1 to index 10).
What was tested: executing bottom-up build-heap exactly, including sift-downs that continue past one level.
Copied. Paste it into the new chat.Too long to send. Copy the question and solution by hand.