Project ForgeConsider a max-heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4 (1-indexed, array index i's children are at 2i and 2i+1). Now consider that a value 35 is inserted into this heap. After insertion, the new heap is
- A40, 30, 20, 10, 15, 16, 17, 8, 4, 35
- 40, 35, 20, 10, 30, 16, 17, 8, 4, 15
- C40, 30, 20, 10, 35, 16, 17, 8, 4, 15
- D40, 35, 20, 10, 15, 16, 17, 8, 4, 30
Explanation
Insert 35 at index 10 (child of index 5, value 15). 35 > 15, so swap: index 5 becomes 35, index 10 becomes 15. Now compare index 5 (35) with its parent, index 2 (value 30): 35 > 30, so swap: index 2 becomes 35, index 5 becomes 30. Compare index 2 (35) with its parent, index 1 (value 40): 35 < 40, stop. Final array: 40, 35, 20, 10, 30, 16, 17, 8, 4, 15.
Source: GATE CS 2015 (Session 1 / 7th Feb Shift 1) (2015)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.