jsschools

Heap

A complete binary tree stored in an array satisfying the heap property — every parent is >= (max-heap) or <= (min-heap) its children.

Spec ↗

Syntax

// Stored as a 0-indexed array. For node at index i:
//   parent:      Math.floor((i - 1) / 2)
//   left child:  2 * i + 1
//   right child: 2 * i + 2

Parameters

NameTypeRequiredDescription
compareFn (a, b) => number No Determines ordering. Return negative to place a before b (min at top). Defaults to (a, b) => a - b (min-heap).

Returns

Heap — A new Heap instance backed by an array.

Examples

class Heap {
  #data; #cmp;
  constructor(cmp = (a, b) => a - b) { this.#data = []; this.#cmp = cmp; }
  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 top = this.#data[0];
    const last = this.#data.pop();
    if (this.#data.length) { this.#data[0] = last; this.#siftDown(0); }
    return top;
  }
  #siftUp(i) {
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (this.#cmp(this.#data[i], this.#data[p]) >= 0) break;
      [this.#data[i], this.#data[p]] = [this.#data[p], this.#data[i]];
      i = p;
    }
  }
  #siftDown(i) {
    const n = this.#data.length;
    while (true) {
      let best = i, l = 2*i+1, r = 2*i+2;
      if (l < n && this.#cmp(this.#data[l], this.#data[best]) < 0) best = l;
      if (r < n && this.#cmp(this.#data[r], this.#data[best]) < 0) best = r;
      if (best === i) break;
      [this.#data[i], this.#data[best]] = [this.#data[best], this.#data[i]];
      i = best;
    }
  }
}
const h = new Heap();
[5, 1, 3, 2, 4].forEach(v => h.push(v));
console.log(h.peek(), h.pop(), h.pop());
Output 
1 1 2

// Heap sort in-place
function heapSort(arr) {
  const n = arr.length;
  for (let i = Math.floor(n/2) - 1; i >= 0; i--) siftDown(arr, i, n);
  for (let end = n - 1; end > 0; end--) {
    [arr[0], arr[end]] = [arr[end], arr[0]];
    siftDown(arr, 0, end);
  }
  return arr;
}
function siftDown(arr, i, n) {
  while (true) {
    let max = i, l = 2*i+1, r = 2*i+2;
    if (l < n && arr[l] > arr[max]) max = l;
    if (r < n && arr[r] > arr[max]) max = r;
    if (max === i) break;
    [arr[i], arr[max]] = [arr[max], arr[i]]; i = max;
  }
}
console.log(heapSort([3, 1, 4, 1, 5, 9, 2, 6]));
Output 
[ 1, 1, 2, 3, 4, 5, 6, 9 ]

Notes

| Operation | Best | Avg | Worst | Space | |-----------|---------|---------|---------|-------| | Peek | O(1) | O(1) | O(1) | O(1) | | Push | O(1) | O(log n)| O(log n)| O(1) | | Pop | O(log n)| O(log n)| O(log n)| O(1) | | Build | O(n) | O(n) | O(n) | O(n) | | Heap sort | O(n log n)|O(n log n)|O(n log n)|O(1)| Building a heap from n elements via repeated sift-down is O(n) (not O(n log n)) — a non-obvious but important result.

See also