Consider a max heap, represented by the array 400, 300, 200, 100, 150, 160,…
2021
Consider a max heap, represented by the array 400, 300, 200, 100, 150, 160, 170, 80, 40. What will be the new heap after insertion of 350?
- A.
400, 300, 200, 100, 150, 160, 170, 80, 40, 350
- B.
400, 350, 200, 100, 300, 160, 170, 80, 40, 150
- C.
400, 300, 200, 100, 350, 160, 170, 80, 40, 150
- D.
400, 350, 200, 100, 150, 160, 170, 80, 40, 300
Attempted by 226 students.
Show answer & explanation
Correct answer: B
Step 1: Start with the max heap array: 400, 300, 200, 100, 150, 160, 170, 80, 40.
Step 2: Insert 350 at the end of the array. New array: 400, 300, 200, 100, 150, 160, 170, 80, 40, 350.
Step 3: Compare 350 with its parent (40) at index 4 (0-based). Since 350 > 40, swap them.
Step 4: Array becomes: 400, 300, 200, 100, 350, 160, 170, 80, 40, 40.
Step 5: Now 350 is at index 4. Compare with its parent (300) at index 1. Since 350 > 300, swap them.
Step 6: Array becomes: 400, 350, 200, 100, 300, 160, 170, 80, 40, 40.
Step 7: Now 350 is at index 1. Compare with its parent (400) at index 0. Since 350 < 400, no further swaps are needed.
Final heap array: 400, 350, 200, 100, 300, 160, 170, 80, 40, 40.