DAY 22 / 30 · WEEK 4

Heaps & Priority Queues

Goal of the day

• Recognize the heap property (every parent must be less than or equal to both of its children, for a min-heap) and understand why a complete binary tree can be stored as a flat array using index math, instead of pointers.
• Implement insert (push to the end, then bubble up) and extractMin (swap the root with the last element, shrink the array, then bubble down) directly on a plain array — the version interviewers actually expect, not a tree of Node objects.
• Know the complexity of every heap operation, including the surprising O(n) cost of building a heap from an existing array, and understand why bubbling down must always check both children, not just the left one.

Concept

A binary heap is a complete binary tree — every level is completely filled except possibly the last, which fills left to right with no gaps — that also satisfies the heap property. For a min-heap (today's focus), the heap property says every parent is less than or equal to both of its children, so the root is always the smallest value in the whole structure. A max-heap is the mirror image: every parent is greater than or equal to both children, so the root is always the largest — same code throughout, just flip every comparison.

Because the tree is always complete (no gaps), you never actually need pointers to represent it. Instead, you store the values in a plain array, left to right, level by level, and use index arithmetic to find a node's parent and children: for a node at index i, its children live at index 2i + 1 and index 2i + 2, and its parent lives at index floor((i − 1) / 2). No Node class, no .left/.right references — just an array and three formulas. This is the array-based heap almost every interview question expects, and it's the reason the tree diagram below and the array boxes above it are two views of the exact same data.

Real-life analogy. Think of a hospital ER's triage queue. Patients aren't seen in the order they walked in — the most urgent case is always seen next, no matter how long everyone else has been waiting. That's a min-heap ordered by urgency, and it's the opposite of Day 18's queue: a FIFO queue guarantees first-come-first-served regardless of how important each item is, while a heap-backed priority queue guarantees most-urgent-first regardless of arrival order.

Diagram: array-to-tree index mapping

Diagram: bubble-up, step by step

Interactive visualization: insert + bubble up

Interactive visualization: extract-min + bubble down

The code: a min-heap on a plain array

class MinHeap {
  constructor() {
    this.data = []; // flat array — this IS the whole heap, no nodes, no pointers
  }

  size() { return this.data.length; }
  peek() { return this.data[0]; }               // O(1) — the min always sits at the root

  // index math takes the place of .parent/.left/.right pointers
  parent(i) { return Math.floor((i - 1) / 2); }
  left(i)   { return 2 * i + 1; }
  right(i)  { return 2 * i + 2; }

  insert(val) {
    this.data.push(val);                   // 1. add to the end — the only O(1) place to insert
    this.bubbleUp(this.data.length - 1);   // 2. restore the heap property upward
  }

  bubbleUp(i) {
    while (i > 0) {
      const p = this.parent(i);
      if (this.data[p] <= this.data[i]) break; // parent already smaller or equal — done
      [this.data[p], this.data[i]] = [this.data[i], this.data[p]]; // swap up
      i = p;                                      // keep bubbling from the new position
    }
  }

  extractMin() {
    if (this.data.length === 0) return undefined;
    const min = this.data[0];        // 1. the root is always the minimum
    const last = this.data.pop();    // 2. remove the last element
    if (this.data.length > 0) {
      this.data[0] = last;           // 3. move it to the root to keep the array compact
      this.bubbleDown(0);            // 4. restore the heap property downward
    }
    return min;
  }

  bubbleDown(i) {
    const n = this.data.length;
    while (true) {
      const l = this.left(i), r = this.right(i);
      let smallest = i;
      if (l < n && this.data[l] < this.data[smallest]) smallest = l;
      if (r < n && this.data[r] < this.data[smallest]) smallest = r; // check BOTH children
      if (smallest === i) break;      // neither child is smaller — done
      [this.data[i], this.data[smallest]] = [this.data[smallest], this.data[i]];
      i = smallest;                   // keep bubbling from the new position
    }
  }
}

Line by line:

• parent/left/right are the entire "pointer structure" of this tree — three formulas, no object references. They assume a 0-indexed array, which is what JavaScript gives you by default; a 1-indexed heap would use 2i/2i + 1 for children instead, so mixing the two conventions is the classic off-by-one bug (more on this in Interview Corner).
• insert is always two steps in this order: append to the end (never anywhere else — that's the only spot that keeps the array "complete"), then call bubbleUp starting from that new last index.
• bubbleUp's while loop compares the current node only against its parent (never siblings) and stops the instant the parent is already small enough — that early break is exactly why insert is O(log n) instead of always walking all the way to the root.
• extractMin has a subtle order dependency: min must be read before pop() touches the array, and the this.data.length > 0 guard matters — if the heap had exactly one element, popping it leaves an empty array, and there is no root left to overwrite or bubble down from.
• bubbleDown's two if lines are the heart of the whole lesson: it checks the left child, then separately checks the right child against whatever is currently the smallest candidate — so it always ends up swapping with the smaller of the two, never just "the left one." Skipping the second check is the single most common heap bug (see the trap in Interview Corner).

Dry run: extractMin() bubble-down on [3, 8, 5, 15, 12, 9, 20]

min = arr[0] = 3 (saved as the return value). Pop the last element, 20, and move it into the root — the array entering the loop below is [20, 8, 5, 15, 12, 9].

Two swaps later the heap is [5, 8, 9, 15, 12, 20] and extractMin() returns 3 — matching the interactive visualization above, which uses this exact same starting array.

Complexity

Why build-heap is O(n), not O(n log n): the standard bottom-up algorithm runs bubbleDown starting from the last non-leaf node up through the root — it does not insert elements one at a time. Most nodes in a complete tree live near the bottom, where a bubbleDown call has almost no distance left to travel (a leaf does zero work, the row just above leaves does at most one swap, and so on). Summing that shrinking amount of work across every level of the tree converges to O(n) total. The naive "n inserts, each O(log n)" estimate of O(n log n) overcounts badly, because it assumes every node needs a full root-to-leaf (or leaf-to-root) walk, when in a heap the vast majority of nodes are already close to where they need to be.

Interview corner

• Why is peek() O(1) while insert and extractMin are O(log n)? peek() just reads index 0 — no traversal at all. insert and extractMin both have to restore the heap property, which can require moving a value along one root-to-leaf path, and that path length is bounded by the tree's height, log n.
  ↳ Common follow-up: "Then why isn't insert O(1) amortized, the way array push is?" — Array push is O(1) because nothing else in the array has to change when you append. A heap insert must preserve a structural invariant across the whole tree, not just the tail — the new value can be smaller than values many levels above it, and only a walk up the tree can discover and fix that. The walk is short (log n), but it's essentially never zero.
• What's the classic off-by-one bug in the parent/child index formulas? Mixing indexing conventions — using 2i/2i + 1 for children (correct only for a 1-indexed heap) together with a 0-indexed JavaScript array, or writing the parent formula as Math.floor(i / 2) instead of Math.floor((i - 1) / 2).
  ⚠ Trap: pick one indexing convention and sanity-check it by hand on index 0 (the root has no parent) and index 1/2 (the root's two children) before writing anything else — silently mixing 0-indexed array access with 1-indexed math is the single most common heap bug in interviews.
• When bubbling down, why must you compare against both children instead of just the left one? The heap property requires the parent to be less than or equal to both children, not just the left. If you only ever compare against (and conditionally swap with) the left child, you can end up in a state where the parent is still greater than the right child — the heap property is now silently violated, even though your one comparison "passed."
  ⚠ Trap: always find the smaller of the two children first, then compare the parent against that one value — don't write two independent if-statements that can each trigger their own swap, or you can swap with the larger child by mistake.
• How do bubbleUp and bubbleDown know when to stop early instead of going all the way to the root or a leaf? The heap property is local: the moment a node satisfies "parent ≤ me" (bubbling up) or "me ≤ both my children" (bubbling down), every node on the other side of it was already valid before this operation touched anything — there's nothing left to fix, so the loop breaks immediately. That early exit is exactly why both operations are O(log n) instead of always paying for a full-height walk.
• Why can't you binary search a heap for an arbitrary value? A heap only guarantees an ordering along parent-child paths — the root is the min, but there's no guarantee about how any two siblings, or any two unrelated nodes, compare to each other. Binary search needs a global order that lets you eliminate half the remaining candidates at each step; a heap doesn't provide one. Finding an arbitrary value in a heap is O(n) worst case, same as an unsorted array.

How to talk through it out loud: say the invariant before touching the array — "index i's children live at 2i + 1 and 2i + 2, its parent at floor((i − 1) / 2), and every parent has to be less than or equal to both children." For insert: "push to the end, then bubble up — compare against the parent, swap if it's bigger, stop the moment it isn't." For extractMin: "save the root as the return value, move the last element into the root, shrink the array by one, then bubble down — compare against both children, swap with whichever is smaller, never just the left one." Interviewers are listening for two specific things: whether you get the index math right without hesitating, and whether you remember to check both children on the way down — those are the two places this pattern silently breaks in a live interview.

Practice problems

class KthLargest {
  constructor(k, nums) {
    this.k = k;
    this.heap = [];
    for (const n of nums) this.add(n);
  }

  add(val) {
    this._push(val);
    if (this.heap.length > this.k) this._popMin();
    return this.heap[0]; // root of a size-k min-heap IS the kth largest
  }

  _push(val) {
    this.heap.push(val);
    let i = this.heap.length - 1;
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (this.heap[p] <= this.heap[i]) break;
      [this.heap[p], this.heap[i]] = [this.heap[i], this.heap[p]];
      i = p;
    }
  }

  _popMin() {
    const last = this.heap.pop();
    if (this.heap.length === 0) return;
    this.heap[0] = last;
    let i = 0;
    const n = this.heap.length;
    while (true) {
      const l = 2 * i + 1, r = 2 * i + 2;
      let s = i;
      if (l < n && this.heap[l] < this.heap[s]) s = l;
      if (r < n && this.heap[r] < this.heap[s]) s = r;
      if (s === i) break;
      [this.heap[i], this.heap[s]] = [this.heap[s], this.heap[i]];
      i = s;
    }
  }
}

function lastStoneWeight(stones) {
  const heap = []; // max-heap: same code as MinHeap, comparisons flipped

  function push(val) {
    heap.push(val);
    let i = heap.length - 1;
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (heap[p] >= heap[i]) break; // parent already >= — no swap needed
      [heap[p], heap[i]] = [heap[i], heap[p]];
      i = p;
    }
  }

  function pop() {
    const top = heap[0];
    const last = heap.pop();
    if (heap.length > 0) {
      heap[0] = last;
      let i = 0;
      const n = heap.length;
      while (true) {
        const l = 2 * i + 1, r = 2 * i + 2;
        let s = i;
        if (l < n && heap[l] > heap[s]) s = l; // largest child wins for a max-heap
        if (r < n && heap[r] > heap[s]) s = r;
        if (s === i) break;
        [heap[i], heap[s]] = [heap[s], heap[i]];
        i = s;
      }
    }
    return top;
  }

  stones.forEach(push);
  while (heap.length > 1) {
    const a = pop(), b = pop(); // a >= b, the two heaviest stones
    if (a !== b) push(a - b);
  }
  return heap.length ? heap[0] : 0;
}

function topKFrequent(nums, k) {
  const freq = new Map();
  for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);

  const heap = []; // min-heap of [count, value] pairs, ordered by count, capped at size k

  function push(item) {
    heap.push(item);
    let i = heap.length - 1;
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (heap[p][0] <= heap[i][0]) break;
      [heap[p], heap[i]] = [heap[i], heap[p]];
      i = p;
    }
  }

  function popMin() {
    const last = heap.pop();
    if (heap.length === 0) return;
    heap[0] = last;
    let i = 0;
    const n = heap.length;
    while (true) {
      const l = 2 * i + 1, r = 2 * i + 2;
      let s = i;
      if (l < n && heap[l][0] < heap[s][0]) s = l;
      if (r < n && heap[r][0] < heap[s][0]) s = r;
      if (s === i) break;
      [heap[i], heap[s]] = [heap[s], heap[i]];
      i = s;
    }
  }

  for (const [val, count] of freq) {
    push([count, val]);
    if (heap.length > k) popMin(); // evict the least-frequent entry once we exceed k
  }
  return heap.map(([count, val]) => val);
}

Quiz