Min-Heap and Max-Heap

Min-heaps and max-heaps differ only in their comparison direction; sift-up after push and sift-down after pop restore the heap property in O(log n) time.

5 min read Level 2/5 #dsa#heap#min-heap

What you'll learn

Implement a MinHeap class with push, pop, and peek in JavaScript
Trace sift-up and sift-down on a concrete example
Convert a MinHeap into a MaxHeap by flipping one comparison

JavaScript has no built-in heap, so we build one on top of a plain array. The only difference between a min-heap and a max-heap is which value “wins” a comparison — every other line of code is identical.

Sift-Up (after push)

When a new value is appended to the end of the array it may be smaller than its parent, violating the min-heap property. Sift-up repeatedly swaps the node with its parent while the parent is larger:

class MinHeap {
  #data = [];

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

  peek() { return this.#data[0]; }   // O(1)

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

  #siftUp(i) {
    const d = this.#data;
    while (i > 0) {
      const p = (i - 1) >> 1;       // parent index
      if (d[p] <= d[i]) break;      // heap property satisfied
      [d[p], d[i]] = [d[i], d[p]];  // swap
      i = p;
    }
  }
}

Sift-Down (after pop)

Pop removes the root (the minimum). To fill the gap, move the last element to index 0 and sift-down: repeatedly swap it with the smaller of its two children until it is smaller than both children or reaches a leaf:

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

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

Complete MinHeap

class MinHeap {
  #data = [];

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

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

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

  #siftUp(i) {
    const d = this.#data;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (d[p] <= d[i]) break;
      [d[p], d[i]] = [d[i], d[p]];
      i = p;
    }
  }

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

// Usage
const h = new MinHeap();
[5, 3, 8, 1, 4].forEach(v => h.push(v));
console.log(h.peek()); // 1
console.log(h.pop());  // 1
console.log(h.pop());  // 3

Converting to a MaxHeap

Flip every < to > (and <= to >=) in the sift methods. Only the comparisons change — the index arithmetic is identical.

Up Next

Learn how to build a heap from an existing array in O(n) time — faster than pushing elements one by one.

Heapify — Building a Heap in O(n) →