Practice question · Put in order
The value 45 is inserted into the max-heap stored as 50, 30, 40, 10, 20, 35, 25. Order what happens.
- 45 is compared with its parent 10 and, being larger, swaps with it
- 45 is larger than 30, so they swap and 45 arrives at index 1
- 45 is compared with the root 50, is smaller, and stops there
- 45 is placed at the next open leaf, index 7, below the node holding 10
- 45 is now at index 3 and is compared with its parent 30
Hints
- Insertion always begins at the next open leaf and then sifts upwards.
- The sifting stops the moment the new value meets a parent that is already larger.
Show the answer
- 45 is placed at the next open leaf, index 7, below the node holding 10
- 45 is compared with its parent 10 and, being larger, swaps with it
- 45 is now at index 3 and is compared with its parent 30
- 45 is larger than 30, so they swap and 45 arrives at index 1
- 45 is compared with the root 50, is smaller, and stops there
Why
The new value enters at the bottom and climbs only while it beats its parent, stopping under 50. Two swaps suffice, and in general the climb is at most the height of the tree, which is why insertion is logarithmic rather than linear despite touching the whole path.
Practise Heaps and Priority Management
The app has 6 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.