Topic notebook / 06
Heaps & priority
A heap returns the smallest or largest priority without sorting every item after every change.
What to look for
- Choose the priority, not just the stored value.
- Remember Python heapq is a min-heap.
- Keep only the candidates you still need.
Work through a question
3 available010203
Choose the Popular Stops
A shuttle records numeric stop IDs for each visit. Return k stops ordered from most visited to least visited. Break frequency ties by the smaller stop ID, even at the cutoff.
Medium / Frequency map + bounded heap / interactiveJoin Cable Reels with Less Work
A technician must join all cable reels into one. Joining lengths a and b costs a + b units of work, and the joined reel can be used again. Return the minimum total work, not the final cable length.
Medium / Min-heap + greedy merging / interactiveReport the Middle Sensor Reading
Sensor readings arrive one at a time. Return the median after every arrival. For an even number of readings, average the two middle values; keep duplicate readings as separate observations.
Hard / Two balanced heaps / interactiveWhere this leads
Return to the roadmap to try a different kind of problem.