Heaps, Intervals & Scheduling

Anything phrased as "the k most frequent", "the k closest", or "merge these sorted streams" is a heap problem, whatever the wording around it suggests. The family shows up often enough at Google that it deserves its own home. A heap hands you the smallest (or largest) element in O(1) and reorders itself in O(log n) on each push or pop. That single property is what lets you answer top-k questions without paying to sort the entire input.

Two ideas cover almost everything here. The first is the size-k heap: keep only k elements on the heap and evict the worst one whenever a better candidate arrives, so you never sort all n items. The second is the k-way merge: load the front of every sorted source into one heap, pop the global minimum, and pull the next item from whichever source it came from. Learn those two and the variants are bookkeeping.