The question this module answers: how do you keep the best few items ready while items keep arriving? Sorting answers "what's the smallest?" once, at O(n log n). But when items arrive and leave all the time (requests by priority, events by time, candidates by score), you want the current minimum now, and each insert and removal to be cheap. That structure is a priority queue, and the standard way to build one is a binary heap.
ML context.
- Top-k: the k highest logits for sampling (lesson 9.9), the k nearest embeddings (lesson 9.10), the k most frequent tokens (lesson 9.5).
- Merging sorted streams: k sorted shards or posting lists (lessons 9.7 and 9.11).
- Search: beam search keeps the best partial sequences (lesson 9.12); Dijkstra and A* expand the cheapest frontier node (module 11).
- Scheduling: the next job to run, the next event in a simulation, the request with the earliest deadline.
1. The problem: repeatedly take the minimum
Task: support push(x) and pop_min() in any interleaving.
Either push or pop is O(n). With n = 10⁶ items in a scheduler or a k-NN search, that's 10⁶ operations per call. A heap makes both O(log n): about 20 for a million items.