Heaps & priority queues

The problem a heap exists to solve

If you need the minimum (or maximum) value once, scan the array — O(n). If you need it repeatedly, while the data keeps changing, sorting every time is O(n log n) per query — wasteful. A heap gives you the extreme value in O(1) and lets you add or remove in O(log n), which is the sweet spot for "keep asking me for the biggest one" problems.

The one rule: parent beats children

A heap is not sorted, and it's not a BST — a node's left child can be bigger or smaller than its right child, the only guarantee is parent-vs-children. That weaker guarantee is exactly what makes insert and remove-min cheaper than keeping the whole thing sorted.

Sift-up (insert) and sift-down (remove) — the two moves

Insert always adds at the very end of the array, then "bubbles" it up while it's smaller than its parent. Removing the min always takes the last element, drops it at the root, then "sinks" it down while it's bigger than its smallest child. Both are O(log n) because they only ever travel the height of the tree.

class MinHeap {
  #data = [];

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

  push(val) {
    this.#data.push(val);
    this.#siftUp(this.#data.length - 1);
  }

  pop() {
    const min = this.#data[0];
    const last = this.#data.pop();
    if (this.#data.length > 0) {
      this.#data[0] = last;
      this.#siftDown(0);
    }
    return min;
  }

  #siftUp(i) {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.#data[parent] <= this.#data[i]) break;
      [this.#data[parent], this.#data[i]] = [this.#data[i], this.#data[parent]];
      i = parent;
    }
  }

  #siftDown(i) {
    const n = this.#data.length;
    while (true) {
      let smallest = i;
      const left = 2 * i + 1, right = 2 * i + 2;
      if (left < n && this.#data[left] < this.#data[smallest]) smallest = left;
      if (right < n && this.#data[right] < this.#data[smallest]) smallest = right;
      if (smallest === i) break;
      [this.#data[i], this.#data[smallest]] = [this.#data[smallest], this.#data[i]];
      i = smallest;
    }
  }
}

The top-K pattern

This is where heaps earn their keep: finding the k largest elements out of n. Sorting everything is O(n log n). A heap does it in O(n log k) — and when k is small relative to n, that's a real win.

// k largest elements — keep a MIN-heap of size k (counter-intuitive but correct)
function kLargest(nums, k) {
  const heap = new MinHeap();
  for (const num of nums) {
    heap.push(num);
    if (heap.size() > k) heap.pop(); // evict the smallest — keep only the top k
  }
  return heap; // contains exactly the k largest, unsorted among themselves
}

The trick that trips people up: for "k largest," you use a min-heap, not a max-heap — because you want to cheaply evict the smallest of your current top-k candidates the moment a bigger one shows up. The heap's root is always "the next one to kick out," which is the smallest of the keepers.

Building a heap from an array in O(n), not O(n log n)

Pushing n elements one at a time costs O(n log n) — each push is O(log n). But if you already have the full array upfront, you can build the heap faster: place all elements as-is, then sift-down starting from the last non-leaf node backward to the root.

function heapify(arr) {
  const n = arr.length;
  // last non-leaf node is at index Math.floor(n/2) - 1 — every index after that is a leaf
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    siftDown(arr, i, n);
  }
  return arr;
}

The two-heap pattern — running median of a data stream

A single heap gives you the min or the max. Finding the median of a growing stream needs both at once — the classic trick is to split the data across two heaps that meet in the middle.

class MedianFinder {
  #small = new MaxHeap(); // same MinHeap code, comparisons flipped — holds the smaller half
  #large = new MinHeap(); // holds the larger half

  addNum(num) {
    this.#small.push(num);
    this.#large.push(this.#small.pop()); // always route through #small first, then rebalance

    if (this.#small.size() < this.#large.size()) {
      this.#small.push(this.#large.pop()); // keep #small equal-or-one-more than #large
    }
  }

  findMedian() {
    if (this.#small.size() > this.#large.size()) return this.#small.peek();
    return (this.#small.peek() + this.#large.peek()) / 2;
  }
}

Every insert is O(log n), and reading the median is O(1) — compare that to re-sorting on every insert (O(n log n) each time) or inserting into a sorted array (O(n) shifting each time). The two-heap split is what makes a streaming median tractable at all.

See it sink

Watch the last element take the root's place and then sink. It only ever follows the smaller child, so it touches one node per level — that is the log n.

Recognizing it in an unseen problem

• "Top K," "k-th largest/smallest," "k closest points"
• Merging k sorted lists/arrays — a heap tracks "the smallest unmerged element" across all of them
• You need repeated access to a min/max while the data set keeps changing (a scheduler, a running median)
• "Running median," "median of a stream" → the two-heap pattern specifically
• A brute force would re-sort after every update — that's the tell a heap should replace it