heap.js

class Heap {
  constructor(comparator) {
    this.elements = [];
    this.end = -1;
    this.cmp = comparator || ((a, b) => a - b);
  }

  getLeft(n) {
    return (2 * (n + 1)) - 1;
  }

  getRight(n) {
    return 2 * (n + 1);
  }

  getParent(n) {
    return Math.floor((n - 1) / 2);
  }

  swap(i, j) {
    const tmp = this.elements[i];
    this.elements[i] = this.elements[j];
    this.elements[j] = tmp;
  }

  heapify(pos) {
    // assume the subtrees are valid heaps
    // therefore we just swap if violating, and recurse
    const lhs = this.getLeft(pos);
    const rhs = this.getRight(pos);

    let smallest = pos;
    if (lhs <= this.end &&
        this.cmp(this.elements[smallest], this.elements[lhs]) > 0) {
      smallest = lhs
    }
    if (rhs <= this.end &&
        this.cmp(this.elements[smallest], this.elements[rhs]) > 0) {
      smallest = rhs
    }
    if (smallest != pos) {
      // swap and heapify
      this.swap(pos, smallest);
      this.heapify(smallest);
    }
  }

  push(e) {
    let pos = ++this.end;
    this.elements[pos] = e;

    // swap with parent until heap condition is satisfied
    while (true) {
      if (this.cmp(this.elements[this.getParent(pos)], e) >= 0) {

        this.swap(pos, this.getParent(pos));
        pos = this.getParent(pos);
      } else {
        break;
      }
    }
  }

  pop() {
    if (this.end < 0) {
      return undefined;
    }

    const output = this.elements[0];

    // move the last element to the front
    this.elements[0] = this.elements[this.end];
    --this.end;

    // heapify
    this.heapify(0);

    return output;
  }

  len() {
    return this.end + 1;
  }
}