Problem context and objectives
Mission briefing
Matchmaking coordinator · Urgent players and jobs compete for limited slots
Keep the best next candidate available without sorting everything again: The Median Balance.
A stale priority frontier increases wait time for everyone.
How you win
- 1Recognize when Two-heap median matches the clues
- 2Keep this true after every move: every lower value is no greater than every upper value and heap sizes differ by at most one
- 3Reach the result within O(n log n)
Rules and pressure
- Target cost: O(n log n)
- State rule: every lower value is no greater than every upper value and heap sizes differ by at most one
Lesson 1 of 3
Live algorithm trace
Two-heap median
Complete execution1 of 6
5
next
15
1
3
Initialize the lower max-heap and upper min-heap.
1
lower = max heap; upper = min heap2
insert into the matching half3
rebalance if sizes differ by more than one4
if sizes match: average roots5
otherwise use the larger heap root6
record each medianlower = []upper = []
Truth to preserve / Cost target
Truth to preserve
every lower value is no greater than every upper value and heap sizes differ by at most one
Cost target
O(n log n)
A max-heap stores the lower half and a min-heap stores the upper half. Rebalance until their sizes differ by at most one, so the median is always available at their roots.
Your call · What should guide every step of this algorithm?