BinaryHeap

BinaryHeap.ts

export default class BinaryHeap<T> {
  constructor(orderComparator: OrderComparator<T>) {
    this.orderComparator = orderComparator;
    this.values = [];
  }

  private orderComparator: OrderComparator<T>;
  private values: T[];

  get length(): number {
    return this.values.length;
  }

  peek(): T {
    return this.values[0];
  }

  push(element: T): void {
    this.values.push(element);

    if (this.values.length >= 2) {
      this.sinkDown(this.values.length - 1);
    }
  }

  pop(): T {
    if (this.values.length === 1) return this.values.pop()!;

    const rootValue = this.peek();

    this.values[0] = this.values.pop()!;
    this.bubbleUp(0);

    return rootValue;
  }

  private sinkDown(at: number): void {
    const parent = Math.floor((at - 1) / 2);

    if (
      this.values[parent] !== undefined &&
      this.orderComparator(this.values[at], this.values[parent]) > 0
    ) {
      [this.values[at], this.values[parent]] = [
        this.values[parent],
        this.values[at]
      ];

      this.sinkDown(parent);
    }
  }

  private bubbleUp(at: number): void {
    const left = at * 2 + 1;
    const right = at * 2 + 2;
    let largest = at;

    if (
      this.values[left] !== undefined &&
      this.orderComparator(this.values[left], this.values[largest]) > 0
    ) {
      largest = left;
    }

    if (
      this.values[right] !== undefined &&
      this.orderComparator(this.values[right], this.values[largest]) > 0
    ) {
      largest = right;
    }

    if (largest !== at) {
      [this.values[largest], this.values[at]] = [
        this.values[at],
        this.values[largest]
      ];

      this.bubbleUp(largest);
    }
  }

  static fromArray<T>(array: T[], orderComparator: OrderComparator<T>) {
    const heap = new BinaryHeap<T>(orderComparator);

    for (const element of array) {
      heap.push(element);
    }

    return heap;
  }
}

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