advanced pattern

Top K Elements (Heap)

Use a heap (priority queue) to efficiently find or maintain the K largest/smallest elements.

Time

O(n log k)

Space

O(k)

🧠Mental Model

“A bouncer at an exclusive club with capacity K. Only the top K VIPs stay - when someone new arrives, compare with the least VIP and swap if needed.”

Verbal cue: Keep K best, replace the worst if something better comes.

🎯Recognition Triggers

When you see these patterns in a problem, consider this approach:

k largestk smallestk most frequentk closesttop kstreaming data

📝Code Template

Top K Elements (Heap) Template

1// JavaScript doesn't have built-in heap
2// Use array-based approach or import a library
3class MinHeap {
4  constructor() { this.heap = []; }
5  
6  push(val) {
7    this.heap.push(val);
8    this.bubbleUp(this.heap.length - 1);
9  }
10  
11  pop() {
12    const min = this.heap[0];
13    const last = this.heap.pop();
14    if (this.heap.length > 0) {
15      this.heap[0] = last;
16      this.bubbleDown(0);
17    }
18    return min;
19  }
20  
21  peek() { return this.heap[0]; }
22  size() { return this.heap.length; }
23  
24  bubbleUp(i) {
25    while (i > 0) {
26      const parent = Math.floor((i - 1) / 2);
27      if (this.heap[parent] <= this.heap[i]) break;
28      [this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
29      i = parent;
30    }
31  }
32  
33  bubbleDown(i) {
34    while (true) {
35      let smallest = i;
36      const left = 2 * i + 1, right = 2 * i + 2;
37      if (left < this.heap.length && this.heap[left] < this.heap[smallest]) smallest = left;
38      if (right < this.heap.length && this.heap[right] < this.heap[smallest]) smallest = right;
39      if (smallest === i) break;
40      [this.heap[smallest], this.heap[i]] = [this.heap[i], this.heap[smallest]];
41      i = smallest;
42    }
43  }
44}

Complexity rationale: Each of n elements may trigger a heap operation of O(log k). Heap size is bounded by k.

💡Interview Tips

1For k largest, use min-heap; for k smallest, use max-heap
2QuickSelect is O(n) average but O(n²) worst case - mention trade-off
3Streaming use case: heap shines when data arrives one at a time

⚠️Common Mistakes

✕Using max-heap when min-heap is needed (and vice versa)
✕Forgetting Python heapq is min-heap only
✕Not handling ties correctly in frequency problems