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

Part 14 of 16 · ~3 min

Heaps & Priority Queues

Recognize this by: "top K," "K largest or smallest," "the Kth largest," or any question that keeps asking for the current min or max of a collection that keeps changing underneath it, where sorting the entire thing every time would be overkill.

Registration week, the planner wants a live "most in-demand right now" panel ranked by waitlist size, updated continuously without re-sorting the entire list on every single change. A binary heap — a complete binary tree packed into a flat array, where every parent beats its children by the heap's ordering — is built for exactly that: adding a value or pulling off the current min/max both cost O(log n), and a peek at the top is free, O(1). Sort the whole catalog first and slice off the top K instead, and the bill is O(n log n) up front regardless of how small K turns out to be — real waste once K is a lot smaller than the catalog it's drawn from.

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 topKMostRequested(waitlistCounts, k) {
  const minHeap = new MinHeap();          // a MIN-heap tracks the K LARGEST counts
  for (const count of waitlistCounts) {
    minHeap.push(count);
    if (minHeap.size > k) minHeap.pop();  // evict the current smallest past capacity k
  }
  return minHeap.data;
}

A min-heap answering a "K largest" question reads like a contradiction until you trace through what's actually being tracked: holding onto the K biggest counts means the one item you'll need to throw out the instant a bigger one shows up is whichever of those K is smallest. Put the smallest item at the top of the structure and eviction becomes trivial — which is exactly what a min-heap gives you, for O(log k) per operation rather than scanning a plain array for the minimum every time. Swap in a max-heap and the identical trick tracks the K smallest values instead.

A few other problems quietly reduce to this same shape, and it's worth having names ready for them. Merging several already-sorted waitlists into one ranked queue works by keeping a heap of each list's current front entry. Finding the quickest route between two buildings on a weighted campus map is Dijkstra's algorithm, which leans on a heap to always surface the next-closest unvisited stop. And tracking the running median of exam scores as they come in one at a time is a job for two heaps meeting in the middle, one holding the lower half and one the upper.

Heaps & Priority Queues on Code Lab.