Lesson 18.4 · Heaps and Priority Queues
Two Heaps for a Running Median
A max-heap holds the smaller half and a min-heap the larger half; their tops are the middle values.
12 min
Think of it like this
Two teams lined up facing each other across a gap, short people on the left, tall on the right. The tallest person on the short team and the shortest on the tall team stand right at the gap: that's where the median is.
1.Keep the halves balanced
low is a max-heap (the smaller half), high a min-heap (the larger half). To add x: push it into low, move low's top into high (so every value in low ≤ every value in high), then if high became bigger, move its top back. low always has the same size or one more.
Median: if the sizes differ, low.peek(); otherwise the average of both tops. Each add is O(log n), each median O(1).
add 5, 15, 1, 3low (max-heap)(list)
high (min-heap)(list)
empty
Step 1/4Add 5. Median 5.
Remember
- low = max-heap of the smaller half, high = min-heap of the larger half.
- Rebalance after every add.
- Also used to pick the best affordable option over time (IPO).
Common mistakes
- Integer division when averaging (use / 2.0).
- Forgetting to route through the other heap, which breaks the ordering between halves.