Top-K Elements — Heaps Without Tears

"Find the K largest / K most frequent / Kth smallest" — the Top-K family. The naive answer is sort everything O(n log n); the pattern answer is a heap of size K → O(n log k).

The size-K heap trick

To find the K largest items, keep a min-heap of size K (yes, min — counterintuitive but correct):

// For each item:
//   push into min-heap
//   if heap size > K, pop the smallest
// Survivors after the full pass = the K largest.
// The heap's root = the Kth largest — the "bouncer" guarding entry.

Why min-heap for largest? The root is the weakest of the current top K — exactly the one to evict when something bigger arrives. Say that sentence in an interview and the pattern is clearly yours.

JavaScript reality check

JS has no built-in heap (Python has heapq, Java has PriorityQueue). For small K in an interview, honestly say: "JS lacks a native heap — for this input size I'll sort at O(n log n), but with a heap it's O(n log k)". Naming the better complexity even while coding the simpler one scores nearly full marks. If asked to implement, a binary min-heap is ~25 lines: array-backed, parent at (i-1)>>1, children at 2i+1, 2i+2, bubble-up on push, sift-down on pop.

The combo: frequency + Top-K

// "K most frequent elements" = two patterns chained:
// 1. HashMap frequency count            (the hashmap pattern)
// 2. Top-K on the counts                (this pattern)
const freq = new Map();
for (const x of nums) freq.set(x, (freq.get(x) ?? 0) + 1);
return [...freq.entries()]
  .sort((a, b) => b[1] - a[1])
  .slice(0, k)
  .map(([val]) => val);

Spot it when…

• The letter K appears: K largest, K closest points, Kth smallest, top K frequent.
• Streaming data where you can't hold everything — a size-K heap uses O(k) memory.

Bonus: Kth largest also has an O(n)-average QuickSelect solution — mention it as the follow-up answer.