Skip to main content

Checkpoint: Streaming Top-K

intermediate28 min readLesson 128 of 148

Prove the heap discipline: keep the K largest of a stream in O(log K) per element.

The task

Implement TopK (see the challenge). The bounded min-heap is the canonical streaming algorithm: the heap holds candidates, its root is the weakest survivor, and each new value either evicts the root or is discarded in O(1). Report must sort K ≤ 5 elements — trivial — but the heap must never exceed K and must always contain the true top-K.

Passing this proves you can turn the module's index arithmetic into a real online algorithm — the pattern behind leaderboards, percentile trackers, and dedup-by-similarity in production.

Next module: files as bytes — binary formats and robust parsing.