Heap.ts

// Fork from https://github.com/yangshun/lago
// https://github.com/yangshun/lago/blob/master/src/data-structures/Heap.ts

export default class Heap {
  private heap: number[] = [];
  static readonly HeapType = { Min: 'Min', Max: 'Max' } as const;
  private compare: (value1: number, value2: number) => boolean

  constructor (type: typeof Heap.HeapType.Min | typeof Heap.HeapType.Max) {
    this.compare =
      type === Heap.HeapType.Min
        ? (value1: number, value2: number) => value1 < value2
        : (value1: number, value2: number) => value1 > value2
  }

  get size (): number {
    return this.heap.length
  }

  isEmpty (): boolean {
    return this.size === 0
  }

  private getRightChildIndex (index: number): number {
    return 2 * index + 2
  }

  private getLeftChildIndex (index: number): number {
    return 2 * index + 1
  }

  private getParentIndex (index: number): number {
    return Math.floor((index - 1) / 2)
  }

  private hasLeftChild (index: number): boolean {
    return this.getLeftChildIndex(index) < this.heap.length
  }

  private hasRightChild (index: number): boolean {
    return this.getRightChildIndex(index) < this.heap.length
  }

  private hasParent (index: number): boolean {
    return this.getParentIndex(index) >= 0
  }

  private swap (index1: number, index2: number): void {
    [this.heap[index1], this.heap[index2]] = [
      this.heap[index2],
      this.heap[index1],
    ]
  }

  peek (): number | null {
    return this.isEmpty() ? null : this.heap[0]
  }

  extract (): number | null {
    if (this.isEmpty()) return null

    this.swap(0, this.size - 1)
    const result = this.heap.pop()!
    this.heapifyDown()
    return result
  }

  insert (value: number): void {
    this.heap.push(value)
    this.heapifyUp()
  }

  private heapifyUp (): void {
    let index = this.heap.length - 1
    let parentIndex = this.getParentIndex(index)
    while (
      this.hasParent(index) &&
      this.compare(this.heap[index], this.heap[parentIndex])
    ) {
      this.swap(index, parentIndex)
      index = parentIndex
      parentIndex = this.getParentIndex(index)
    }
  }

  private heapifyDown (): void {
    let index = 0
    let leftChildIndex = this.getLeftChildIndex(index)
    let rightChildIndex = this.getRightChildIndex(index)
    while (
      (this.hasLeftChild(index) &&
        !this.compare(this.heap[index], this.heap[leftChildIndex])) ||
      (this.hasRightChild(index) &&
        !this.compare(this.heap[index], this.heap[rightChildIndex]))
    ) {
      const comparableIndex =
        this.hasRightChild(index) &&
          !this.compare(this.heap[leftChildIndex], this.heap[rightChildIndex])
          ? rightChildIndex
          : leftChildIndex
      this.swap(index, comparableIndex)
      index = comparableIndex
      leftChildIndex = this.getLeftChildIndex(index)
      rightChildIndex = this.getRightChildIndex(index)
    }
  }
}