BinaryHeap.ts

type CompareFn<T> = (a: T, b: T) => number;

class BinaryHeap<T> {
  array: T[];
  compareFn: CompareFn<T>;

  constructor(compareFn: CompareFn<T>) {
    this.compareFn = compareFn;
    this.array = [];
  }

  pop() {
    [this.array[0], this.array[this.array.length - 1]] = [this.array[this.array.length - 1], this.array[0]];
    const e = this.array.pop();
    this.sinkDown(0);
    return e;
  }

  sinkDown(i: number) {
    if (i < 0) return;
    const n = this.array.length;

    while (i < n) {
      let left = i * 2 + 1, right = i * 2 + 2;
      let target = i;

      if (left < n && this.compareFn(this.array[target], this.array[left]) <= 0) {
        target = left;
      }

      if (right < n && this.compareFn(this.array[target], this.array[right]) <= 0) {
        target = right;
      }

      if (target !== i) {
        [this.array[i], this.array[target]] = [this.array[target], this.array[i]];
        i = target;
      } else {
        break;
      }
    }
  }

  push(value: T): number {
    const len = this.array.push(value);
    this.bubbleUp(len - 1);
    return len;
  }

  bubbleUp(i: number): void {
    let parentIdx = Math.floor((i - 1) / 2);
    while (parentIdx >= 0 && this.compareFn(this.array[parentIdx], this.array[i]) <= 0) {
      [this.array[i], this.array[parentIdx]] = [this.array[parentIdx], this.array[i]];
      i = parentIdx;
      parentIdx = Math.floor((i - 1) / 2);
    }
  }
}