0
Challenge · 58Heaps & Top-K

Top-K

Heapsused in ~85% of apps

The most common heap question in a real interview, and the one people get backwards in the first thirty seconds. To keep the k largest values you need a heap that puts the SMALLEST on top, and being able to say why is most of the answer.

Core idea. Hold a heap capped at k. Every arriving value goes in, and if that makes k plus one, throw away the top. Point the heap at the opposite end from the answer you want, so the weakest survivor is the one sitting where it can be discarded in a single move.
Playground, this isn't a screenshot
a heap capped at 3, with the stream going past
empty
the stream
5193728
thrown away
nothing yet
a MIN heap, capped at 3, to keep the 3 LARGEST values. That swap of direction is the part people get backwards
step 1 of 9

To keep the k LARGEST you need a MIN heap, so the weakest survivor sits where you can throw it away in one move.

↑ play a little first, then dig in