heap TS

heap.ts

export const min = (a: number, b: number) => a < b
export const max = (a: number, b: number) => a > b

type Comparetor<T> = (a: T, b: T) => boolean

export class Heap<T = number> {
  private heap: T[] = []
  constructor(private comp: Comparetor<T>) {}

  private parent(i: number) {
    return Math.floor(i-2/2)
  }

  private left(i: number) {
    return Math.floor(i*2 + 1)
  }

  private right(i: number) {
    return Math.floor(i*2 + 2)
  }

  private swap(a: number, b: number) {
    const temp = this.heap[a]
    this.heap[a] = this.heap[b]
    this.heap[b] = temp
  }

  private heapUp() {
    let i = this.heap.length - 1

    let parent = this.parent(i)
    while(i > 0 && this.comp(this.heap[i], this.heap[parent])) {
      this.swap(i, parent)
      i = parent
      parent = this.parent(parent)
    }
  }

  private heapDown() {
    let i = 0

    let left = this.left(i)
    let right = this.right(i)
    while(left < this.heap.length) {
      if (this.heap[right] !== undefined && this.comp(this.heap[right], this.heap[left]) && this.comp(this.heap[right], this.heap[i])) {
        this.swap(i, right)
        i = right
      } else if (this.comp(this.heap[left], this.heap[i])) {
        this.swap(i, left)
        i = left
      } else {
        break
      }
      left = this.left(i)
      right = this.right(i)
    }
  }

  enqueue(v: T) {
    this.heap.push(v)
    this.heapUp()
  }

  dequeue() {
    if (!this.heap.length) return null
    if (this.heap.length === 1) {
      const temp = this.heap.pop()
      return temp as T
    }
    const output = this.heap[0]
    const temp = this.heap.pop()
    this.heap[0] = temp as T
    this.heapDown()
    return output
  }

  peek() {
    return this.heap[0]
  }
}