TypeScriptで優先度付きキューを実装してみた

TypeScriptで優先度付きキューを実装してみました。

※ 実装の詳細については、後日追記します。

type HeapNode<T> = {
  data: T;
  priority: number;
};

class HeapLibrary<T> {
  public comparator: (a: HeapNode<T>, b: HeapNode<T>) => boolean;

  constructor(comparator: (a: HeapNode<T>, b: HeapNode<T>) => boolean) {
    this.comparator = comparator;
  }

  public buildHeap(arr: HeapNode<T>[]): void {
    const middle: number = HeapLibrary.parent(arr.length - 1);
    for (let i = middle; i >= 0; i--) {
      this.heapify(arr, arr.length - 1, i);
    }
  }

  public heapify(arr: HeapNode<T>[], heapEnd: number, i: number): void {
    const l: number = HeapLibrary.left(i);
    const r: number = HeapLibrary.right(i);

    let biggest: number = i;
    if (l <= heapEnd && this.comparator(arr[l], arr[biggest])) biggest = l;
    if (r <= heapEnd && this.comparator(arr[r], arr[biggest])) biggest = r;

    if (biggest !== i) {
      const temp: HeapNode<T> = arr[i];
      arr[i] = arr[biggest];
      arr[biggest] = temp;
      this.heapify(arr, heapEnd, biggest);
    }
  }

  public static left(i: number): number {
    return 2 * i + 1;
  }

  public static right(i: number): number {
    return 2 * i + 2;
  }

  public static parent(i: number): number {
    return Math.floor((i - 1) / 2);
  }
}

class PriorityQueue<T> {
  private heap: HeapNode<T>[];
  private heapLibrary: HeapLibrary<T>;

  constructor(arr: HeapNode<T>[], comparator: (a: HeapNode<T>, b: HeapNode<T>) => boolean) {
    this.heap = [...arr];
    this.heapLibrary = new HeapLibrary<T>(comparator);
    this.heapLibrary.buildHeap(this.heap);
  }

  public isEmpty(): boolean {
    return this.heap.length <= 0;
  }

  public top(): HeapNode<T> {
    return this.heap[0];
  }

  public pop(): HeapNode<T> {
    const temp: HeapNode<T> = this.heap[0];
    this.heap[0] = this.heap[this.heap.length - 1];
    this.heap.pop();
    this.heapLibrary.heapify(this.heap, this.heap.length - 1, 0);
    return temp;
  }

  public insert(t: HeapNode<T>): void {
    this.heap.push(t);
    let i: number = this.heap.length - 1;
    let parent: number = HeapLibrary.parent(i);
    while (
      parent >= 0 &&
      !this.heapLibrary.comparator(this.heap[parent], this.heap[i])
    ) {
      const temp: HeapNode<T> = this.heap[i];
      this.heap[i] = this.heap[parent];
      this.heap[parent] = temp;
      i = parent;
      parent = HeapLibrary.parent(i);
    }
  }
}