Generic Heap Implementation for JS

heap.ts

export interface Comparable<T> {
  compare(a: T, b: T): number;
}

export class Heap<T> {
  #values: T[] = [];
  #id: Comparable<T>;

  constructor(id: Comparable<T>) {
    this.#id = id;
  }

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

  values(): T[] {
    return this.#values.slice();
  }

  add(val: T) {
    this.#values.push(val);
    this.#heapifyUp();
  }

  pop(): T | undefined {
    let size = this.size;
    if (size <= 1) {
      return this.#values.pop();
    }
    this.#swap(0, size - 1);
    let value = this.#values.pop();
    this.#heapifyDown();
    return value;
  }

  clear(): void {
    this.#values = [];
  }

  #offset(a: number, b: number) {
    return this.#id.compare(this.#values[a], this.#values[b]);
  }

  #swap(a: number, b: number) {
    [this.#values[a], this.#values[b]] = [this.#values[b], this.#values[a]];
  }

  #heapifyUp() {
    let index = this.size - 1;
    let parentIndex = this.#parentOf(index);

    while (this.#offset(parentIndex, index) > 0) {
      this.#swap(parentIndex, index);
      index = parentIndex;
      parentIndex = this.#parentOf(index);
    }
  }

  #heapifyDown() {
    let index = 0;
    let lastIndex = this.size - 1;

    while (index < lastIndex) {
      let leftIndex = this.#leftChildOf(index);
      let rightIndex = this.#rightChildOf(index);

      if (leftIndex > lastIndex) {
        break;
      } else if (rightIndex > lastIndex) {
        if (this.#offset(index, leftIndex) > 0) {
          this.#swap(index, leftIndex);
          index = leftIndex;
        } else {
          break;
        }
      } else {
        let leftOffset = this.#offset(index, leftIndex);
        let rightOffset = this.#offset(index, rightIndex);
        if (leftOffset > 0 && rightOffset > 0) {
          if (this.#offset(rightIndex, leftIndex) >= 0) {
            this.#swap(index, leftIndex);
            index = leftIndex;
          } else {
            this.#swap(index, rightIndex);
            index = rightIndex;
          }
        } else if (leftOffset > 0) {
          this.#swap(index, leftIndex);
          index = leftIndex;
        } else if (rightOffset > 0) {
          this.#swap(index, rightIndex);
          index = rightIndex;
        } else {
          break;
        }
      }
    }
  }

  #parentOf(index: number) {
    return (index - 1) / 2 | 0;
  }

  #leftChildOf(index: number) {
    return index * 2 + 1;
  }

  #rightChildOf(index: number) {
    return index * 2 + 2;
  }
}