Implementing a binary heap

Every heap operation restores the invariant along a single path, using one of two helpers.

class MinHeap {
  #items = [];

  constructor(compare = (a, b) => a - b) {
    this.compare = compare;          // pass a comparator for objects
  }

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

  push(value) {
    this.#items.push(value);         // add at the end, keeping it complete
    this.#siftUp(this.#items.length - 1);
  }

  pop() {
    if (!this.#items.length) return undefined;

    const top = this.#items[0];
    const last = this.#items.pop();

    if (this.#items.length) {
      this.#items[0] = last;         // move the last item to the root
      this.#siftDown(0);
    }

    return top;
  }

  #siftUp(i) {
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.compare(this.#items[i], this.#items[parent]) >= 0) break;

      [this.#items[i], this.#items[parent]] = [this.#items[parent], this.#items[i]];
      i = parent;
    }
  }

  #siftDown(i) {
    const n = this.#items.length;

    for (;;) {
      const left = 2 * i + 1;
      const right = left + 1;
      let smallest = i;

      if (left < n && this.compare(this.#items[left], this.#items[smallest]) < 0) smallest = left;
      if (right < n && this.compare(this.#items[right], this.#items[smallest]) < 0) smallest = right;
      if (smallest === i) break;

      [this.#items[i], this.#items[smallest]] = [this.#items[smallest], this.#items[i]];
      i = smallest;
    }
  }
}

Each loop walks at most the height of the tree, so both are O(log n).

The three details people get wrong

1. Pop moves the last element to the root, not a child. Promoting a child breaks completeness.
2. Sift down must compare against both children and swap with the smaller. Comparing only the left corrupts the heap silently.
3. >= 0 in sift up, not > 0 — stopping on equality avoids pointless swaps.

Building from an array in O(n)

function heapify(items, compare) {
  const heap = new MinHeap(compare);
  // Sift down from the last parent backwards. O(n), not O(n log n).
  for (let i = (items.length >> 1) - 1; i >= 0; i--) heap.siftDownAt(items, i);
  return heap;
}

Max-heap for free

Invert the comparator: (a, b) => b - a. Never write a second class — and for objects, compare the field you care about, which is exactly what a priority queue is.