Top K with a Heap
Keep a heap of exactly K elements of the opposite polarity, so the worst survivor is always at the top and cheap to evict.
Heap / Priority QueueO(n log k)New20 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
k largest or smallest
k closest points
k most frequent
The template
Get this into muscle memory, then adapt the condition per problem.
const heap = new MinHeap();
for (const x of items) {
heap.push(x);
if (heap.size > k) heap.pop();
}
return heap.toArray(); Watch Heap: Push and PopIf you are stuck
The generic hint ladder for this pattern, in order.
- 1Full sorting is O(n log n). You only need K of them.
- 2For k largest, a min heap lets you drop the smallest cheaply.
- 3Bucket sort by frequency can beat the heap when counts are bounded.
Drill it
Every problem in the bank that uses this pattern.
0 / 20 solved