DSA Patterns for Coding Interviews: The Techniques Behind Almost Every Problem

Heaps & Priority Queues

The signal: "top K," "K largest/smallest," "the Kth largest element," or anything that needs repeated access to the current minimum or maximum of a changing collection without needing the whole thing fully sorted.

A binary heap — a complete binary tree stored flat in an array, where every parent is smaller (min-heap) or larger (max-heap) than its children — supports insert and extract-min/max in O(log n), and peeking at the min/max in O(1). Sorting the entire input first and then taking the first K, by contrast, costs O(n log n) regardless of how small K is relative to n — real wasted work once K is meaningfully smaller than n.

class MinHeap {
  constructor() { this.data = []; }

  push(val) {
    this.data.push(val);
    let i = this.data.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.data[parent] <= this.data[i]) break;
      [this.data[parent], this.data[i]] = [this.data[i], this.data[parent]];   // bubble up
      i = parent;
    }
  }

  pop() {
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length) {
      this.data[0] = last;
      let i = 0;
      while (true) {
        const left = 2 * i + 1, right = 2 * i + 2;
        let smallest = i;
        if (left < this.data.length && this.data[left] < this.data[smallest]) smallest = left;
        if (right < this.data.length && this.data[right] < this.data[smallest]) smallest = right;
        if (smallest === i) break;
        [this.data[i], this.data[smallest]] = [this.data[smallest], this.data[i]];   // bubble down
        i = smallest;
      }
    }
    return top;
  }

  peek() { return this.data[0]; }
  get size() { return this.data.length; }
}

Top K with a heap

function kLargest(nums, k) {
  const minHeap = new MinHeap();          // a MIN-heap, for the K LARGEST values
  for (const n of nums) {
    minHeap.push(n);
    if (minHeap.size > k) minHeap.pop();  // evict the current smallest once the heap holds more than k
  }
  return minHeap.data;
}

The min-heap-for-K-largest pairing feels backwards the first time you see it, so it's worth stating the reasoning directly: to keep track of the K largest values seen so far, the one you need to be able to find and discard quickly is the smallest one currently being kept — and a min-heap's root gives you exactly that, in O(log k) per operation instead of O(k) for a linear scan. The mirror image — a max-heap to track the K smallest — works by the identical logic, reversed.

The same idea underlies a handful of other problems worth being able to recognize: merging K sorted lists (a heap holding the current front element of each list), Dijkstra's shortest-path algorithm (a heap picks off the next-closest unvisited node), and finding a running median over a data stream (two heaps, split at the median).

Practice this on Code Lab: Heaps & Priority Queues