Heap
How Heap works
Before you start
- Open lesson
Trees
A heap is a binary tree with a stronger shape rule. That lesson covers parents, children, and height.
Why it matters
Schedulers, simulations, and resource managers repeatedly need the most urgent item while priorities change. Sorting the entire collection after every removal or insertion spends most of its work reordering items that are not needed yet. Each round must remove the two largest stones and restore readiness for the next round without sorting all remaining stones again.
Example
Last Stone Weight
Each turn, smash the two heaviest stones. If they differ, push back the difference. Return the last stone's weight, or 0 if none remain.
- Input
- stones = [2, 7, 4, 1, 8, 1]
- Output
- 1
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Last Stone Weight
stones = [2, 7, 4, 1, 8, 1]→1
The baseline, Sort every round, is O(n² log n) · O(1). The better model below keeps this exact input and removes that bottleneck.
For [2, 7, 4, 1, 8, 1], brute force sorts every round before choosing 8 and 7. A heap exposes those two stones, pushes their difference 1, and repairs only its affected paths instead of reordering the whole list.
For [2, 7, 4, 1, 8, 1], store [−2, −7, −4, −1, −8, −1] because heapq exposes its smallest entry. After heapify, −8 is at the root. Two pops produce weights 8 and 7, and pushing −1 represents their difference.
The next rounds pop 4 and 2 and push 2, then pop 2 and 1 and push 1. Two equal 1s disappear, leaving the final 1. Each pop replaces the root with the last entry and sifts it down; each push sifts one new entry up.
0
1
2
3
4
5
children of i: 2i + 1 and 2i + 2 · parent of i: (i − 1) // 2
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.