jsschools

Max-Heap

A heap where the root is always the maximum element, enabling O(1) access to the largest value and O(log n) extract-max.

Spec ↗

Syntax

class MaxHeap extends Heap {
  constructor() { super((a, b) => b - a); }
}

Returns

MaxHeap — A new Max-Heap instance where the maximum element is always at the top.

Examples

class MaxHeap {
  #d = [];
  push(v) { this.#d.push(v); this.#up(this.#d.length - 1); }
  pop() {
    const top = this.#d[0];
    const last = this.#d.pop();
    if (this.#d.length) { this.#d[0] = last; this.#down(0); }
    return top;
  }
  peek() { return this.#d[0]; }
  get size() { return this.#d.length; }
  #up(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.#d[p] >= this.#d[i]) break;
      [this.#d[i], this.#d[p]] = [this.#d[p], this.#d[i]]; i = p;
    }
  }
  #down(i) {
    const n = this.#d.length;
    while (true) {
      let b = i, l = 2*i+1, r = 2*i+2;
      if (l < n && this.#d[l] > this.#d[b]) b = l;
      if (r < n && this.#d[r] > this.#d[b]) b = r;
      if (b === i) break;
      [this.#d[i], this.#d[b]] = [this.#d[b], this.#d[i]]; i = b;
    }
  }
}

// K largest numbers
const heap = new MaxHeap();
[9, 4, 7, 1, 5, 3, 8, 2, 6].forEach(n => heap.push(n));
const k3 = [heap.pop(), heap.pop(), heap.pop()];
console.log(k3);
Output 
[ 9, 8, 7 ]

// Find median of stream using two heaps
// max-heap for lower half, min-heap for upper half
class MedianFinder {
  #lo = new MaxHeap(); // lower half
  #hi = []; // min-heap placeholder
  addNum(n) {
    this.#lo.push(n);
    // balance heaps...
    console.log('peek lower half:', this.#lo.peek());
  }
}
console.log('Two-heap median trick uses max-heap + min-heap');
Output 
Two-heap median trick uses max-heap + min-heap

Notes

| Operation | Best | Avg | Worst | Space | |-----------|------|---------|---------|-------| | Peek max | O(1) | O(1) | O(1) | O(1) | | Push | O(1) | O(log n)| O(log n)| O(1) | | Pop max | O(log n)| O(log n)|O(log n)| O(1) | | Build | O(n) | O(n) | O(n) | O(n) | Heap sort uses a max-heap: build the heap in O(n), then repeatedly extract-max to sort in O(n log n) with O(1) extra space. The classic "K largest in a stream" problem is solved in O(n log k) by maintaining a min-heap of size k.

See also