Past exam question: 2079 Ashwin (Back), Q8(b)
Open in the Padhaiko appConsider the following max heap: 50, 30, 20, 15, 10, 8, 16. Insert a new node with value 60.
Solution
Initial Max-Heap Structure Analysis: The initial heap elements in array form:
Array indices: to . In an array representation of a complete binary tree (0-indexed):
- Root is at index :
50 - Children of node at index : left child at , right child at .
- Parent of node at index : .
Initial tree diagram:
50 [idx 0]
/ \
30 [idx 1] 20 [idx 2]
/ \ / \
15 [idx 3] 10 [idx 4] 8 [idx 5] 16 [idx 6]
Verification of max-heap property: , , .
Insertion at the Next Available Complete Tree Position: To maintain the shape property of a complete binary tree, the new key 60 is placed at the end of the array at index (as the left child of node at index , which is 15):
Tree at this stage:
50
/ \
30 20
/ \ / \
15 10 8 16
/
60 [idx 7]
The max-heap property is violated because child 60 > parent 15. We must heapify-up (percolate-up / swim).
Percolate-Up (Swim) Iteration 1:
- Compare
60at index with its parent at index (value15). - Since , swap element
60with15. - New array:
- Node
60is now located at index .
Tree at this stage:
50
/ \
30 20
/ \ / \
60 10 8 16
/
15Percolate-Up (Swim) Iteration 2:
- Compare
60at index with its parent at index (value30). - Since , swap element
60with30. - New array:
- Node
60is now located at index .
Tree at this stage:
50
/ \
60 20
/ \ / \
30 10 8 16
/
15Percolate-Up (Swim) Iteration 3:
- Compare
60at index with its parent at index (value50, the root). - Since , swap element
60with50. - New array:
- Node
60is now at index (the root). Since it has reached the root, the insertion terminates.
Final Max-Heap Tree and Array: Final array representation:
Final complete binary tree:
60 [idx 0]
/ \
50 [idx 1] 20 [idx 2]
/ \ / \
30 [idx 3] 10 [idx 4] 8 [idx 5] 16 [idx 6]
/
15 [idx 7]
Property Check:
- Root
- Node
- Node
- Node
All parent-child relationships strictly satisfy the max-heap condition in time.
After inserting 60 into the max-heap:
- Final Array Representation:
- Percolate-up Swaps:
- Swap 60 with 15 (at index 3).
- Swap 60 with 30 (at index 1).
- Swap 60 with 50 (at index 0).
Node 60 becomes the new root of the max-heap.