Heap / Priority Queue

How It Works

A heap is a complete binary tree (every level is fully filled except possibly the last, which fills left to right) that satisfies the heap property: in a min-heap, every parent is less than or equal to both its children; in a max-heap, every parent is greater than or equal to both its children. Because it's complete, a heap can be stored compactly in a plain array with no pointers at all. For a node at index i, its children live at 2i + 1 and 2i + 2, and its parent lives at Math.floor((i - 1) / 2). This is exactly how a priority queue is implemented under the hood: the "priority" is whatever comparator you use to order the heap.

The heap property only constrains parent-vs-child, not left-vs-right siblings, so a heap is not fully sorted; it only guarantees the root is the min (or max). That's precisely the trade-off that makes it fast: you get O(1) access to the extreme value without paying the O(n log n) cost of fully sorting everything.

Core operations:

• Peek (root): O(1). The min (or max) is always at index 0.
• Insert: push the new value to the end of the array, then sift up: repeatedly swap it with its parent while it violates the heap property. O(log n) because the tree height is log n.
• Extract-min/max: swap the root with the last element, pop the last element off (that's your answer), then sift down the new root: repeatedly swap it with its smaller (min-heap) child while it violates the heap property. Also O(log n).

// Array-based min-heap
class MinHeap {
  constructor() {
    this.data = [];
  }

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

  size() {
    return this.data.length;
  }

  insert(value) {
    this.data.push(value);
    this.siftUp(this.data.length - 1);
  }

  extractMin() {
    if (this.data.length === 0) return undefined;
    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(index) {
    while (index > 0) {
      const parent = Math.floor((index - 1) / 2);
      if (this.data[parent] <= this.data[index]) break;
      [this.data[parent], this.data[index]] = [
        this.data[index],
        this.data[parent],
      ];
      index = parent;
    }
  }

  siftDown(index) {
    const n = this.data.length;
    while (true) {
      const left = 2 * index + 1;
      const right = 2 * index + 2;
      let smallest = index;

      if (left < n && this.data[left] < this.data[smallest]) smallest = left;
      if (right < n && this.data[right] < this.data[smallest]) smallest = right;
      if (smallest === index) break;

      [this.data[smallest], this.data[index]] = [
        this.data[index],
        this.data[smallest],
      ];
      index = smallest;
    }
  }
}

// Usage: find the k smallest elements
function kSmallest(nums, k) {
  const heap = new MinHeap();
  for (const n of nums) heap.insert(n);
  const result = [];
  for (let i = 0; i < k && heap.size() > 0; i++) {
    result.push(heap.extractMin());
  }
  return result;
}

Common Mistakes

• Off-by-one index math: mixing up 2i + 1/2i + 2 for children or (i - 1) / 2 for the parent, especially forgetting Math.floor and getting a fractional parent index.
• Assuming a heap is fully sorted: it isn't; only the root is guaranteed to be the extreme value, so iterating the raw array expecting sorted order is wrong.
• Forgetting to sift after both insert and extract: insert requires sift-up from the newly added leaf, extract requires sift-down from the new root; skipping either breaks the invariant silently.
• Not handling the empty-heap edge case: calling extractMin() on an empty heap without a guard, or forgetting to check this.data.length > 0 before moving the last element to the root.
• Reaching for a heap when a simple sort would do: for a one-time need of the full sorted order, sorting is simpler; a heap earns its keep when you need repeated access to the current min/max as the collection changes (e.g., streaming data, k-way merge, Dijkstra's algorithm).

Pattern Summary

Reach for a heap whenever a problem repeatedly needs "the smallest/largest so far" while the underlying set keeps changing: top-K problems, merging K sorted lists, running medians, and shortest-path algorithms like Dijkstra's all lean on O(log n) insert/extract instead of re-sorting from scratch. The edge it gives you in interviews is recognizing that "give me the next best option, repeatedly" is a priority-queue problem even when the prompt never uses the word "heap."