Heap

heap.js

function Heap(compare = (target, parent) => target > parent) {
  this.array = [];
  this.compare = compare;
}

Object.defineProperty(Heap.prototype, 'size', { get: function () { return this.array.length; } })

Heap.prototype.peek = function () { return this.array[0]; }

Heap.prototype.pop = function () {
  const top = this.array[0];
  this.sink();

  return top;
}

Heap.prototype.push = function (item) {
  this.array.push(item);
  this.sift();
}

Heap.prototype.sink = function () {
  let index = 0;

  while (index < this.size) {
    const children = index * 2;
    const left = [children + 1, this.array[children + 1]];
    const right = [children + 2, this.array[children + 2]];
    const child = right[1] == null || this.compare(left[1], right[1]) ? left : right;

    this.array[index] = child[1];
    index = child[0];
  }

  this.array.pop();
}

Heap.prototype.sift = function () {
  let index = this.size - 1;
  const target = this.array[index];

  while (index > 0) {
    const parentIndex = Math.ceil(index / 2) - 1;
    const parent = this.array[parentIndex];

    if (!this.compare(target, parent))
      break;

    this.array[parentIndex] = target;
    this.array[index] = parent;
    index = parentIndex;
  }
}

heap.ts

class Heap {
  private array: number[] = [];

  get size() {
    return this.array.length;
  }

  constructor(private compare = (target, parent) => target > parent) { }

  peek() {
    return this.array[0];
  }

  pop() {
    const top = this.array[0];
    this.sink();

    return top;
  }

  push(item: number) {
    this.array.push(item);
    this.sift();
  }

  private sift() {
    let index = this.size - 1;
    const target = this.array[index];

    while (index > 0) {
      const parentIndex = Math.ceil(index / 2) - 1;
      const parent = this.array[parentIndex];

      if (!this.compare(target, parent))
        break;

      this.array[parentIndex] = target;
      this.array[index] = parent;
      index = parentIndex;
    }
  }

  private sink() {
    let index = 0;

    while (index < this.size) {
      const children = index * 2;
      const left = [children + 1, this.array[children + 1]];
      const right = [children + 2, this.array[children + 2]];
      const child = right[1] == null || this.compare(left[1], right[1]) ? left : right;

      this.array[index] = child[1];
      index = child[0];
    }

    this.array.pop();
  }
}