Heapify — Building a Heap in O(n)

If you push n elements into a heap one by one you pay O(log n) per push — O(n log n) total. Heapify does better: it rearranges an existing array in-place in O(n) with no extra memory.

The Algorithm

Leaf nodes already satisfy the heap property vacuously — they have no children to compare against. The last internal node (the parent of the last element) sits at index Math.floor((n - 2) / 2), which equals (n - 1) >> 1 - 1 simplified to (n >> 1) - 1.

Start there and call sift-down on every node back to the root:

function heapify(arr) {
  const n = arr.length;
  // Last internal node index: floor((n - 2) / 2)
  for (let i = (n >> 1) - 1; i >= 0; i--) {
    siftDown(arr, i, n);
  }
  return arr;
}

function siftDown(arr, i, n) {
  while (true) {
    let smallest = i;
    const l = 2 * i + 1;
    const r = 2 * i + 2;
    if (l < n && arr[l] < arr[smallest]) smallest = l;
    if (r < n && arr[r] < arr[smallest]) smallest = r;
    if (smallest === i) break;
    [arr[smallest], arr[i]] = [arr[i], arr[smallest]];
    i = smallest;
  }
}

const data = [9, 4, 7, 1, 8, 3, 6, 5, 2];
heapify(data);
console.log(data[0]); // 1 — root is the minimum

Why O(n) and Not O(n log n)?

The key insight is that most nodes live near the bottom of the tree and sift very short distances.

Total work = sum over all levels of (node count) x (sift distance):

sum_{k=0}^{h} (n / 2^(k+1)) * k  ≈  n * sum_{k=1}^{∞} k / 2^k  =  n * 2  =  O(n)

The geometric series converges to 2, so the total is O(n) regardless of n.

Pushing n elements one by one costs O(n log n) because each push sifts from a leaf all the way up; heapify sifts internal nodes downward where the path lengths are short.

Integration into MinHeap

class MinHeap {
  #data;

  constructor(arr = []) {
    this.#data = arr.slice();       // copy so we don't mutate the input
    this.#heapify();
  }

  #heapify() {
    const n = this.#data.length;
    for (let i = (n >> 1) - 1; i >= 0; i--) {
      this.#siftDown(i);
    }
  }

  // ... push / pop / siftUp / siftDown as before
}

const h = new MinHeap([9, 4, 7, 1, 8, 3]);
console.log(h.peek()); // 1

Up Next

Build a general-purpose PriorityQueue on top of the heap, supporting custom comparators so you can order objects by any field.