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 Living Summit.
A stale priority frontier increases wait time for everyone.
How you win
- 1Recognize when Fixed-size streaming heap matches the clues
- 2Keep this true after every move: after each arrival, the heap contains exactly the k largest values seen
- 3Reach the result within O((initial + additions) log k)
Rules and pressure
- Target cost: O((initial + additions) log k)
- State rule: after each arrival, the heap contains exactly the k largest values seen
Lesson 1 of 3
Live algorithm trace
Fixed-size streaming heap
Complete execution1 of 6
4
root
5
8
2
3
5
10
9
4
Heapify history and remove the smallest until three values remain.
1
heapify initial values2
trim heap to size k3
for each addition4
push the new value5
pop minimum if size exceeds k6
record heap rootk = 3history = [4,5,8,2]additions = [3,5,10,9,4]heap = [4,5,8]trimmed = 2
Truth to preserve / Cost target
Truth to preserve
after each arrival, the heap contains exactly the k largest values seen
Cost target
O((initial + additions) log k)
A min-heap of size k stores the k largest values observed so far. Its root is the kth largest, so each arrival needs at most one insertion and one eviction.
Your call · What should guide every step of this algorithm?