Class PriorityQueue

src/PriorityQueue.ts:1–198

class PriorityQueue<T extends object> {
  private _queue: Array<T>;
  private _size: number = 0;
  private _comparator: ((val: T, parent: T) => number) | null;

  constructor(initialCapacity?: number, comparator?: (val: T, parent: T) => number) {
    const cap = initialCapacity ?? 11;
    const com = comparator ?? null;
    if (cap < 1) {
      throw new Error('initial capacity must be greater than or equal to 1');
    }
    this._queue = new Array<T>(cap);
    this._comparator = com;
  }

  private grow() {
    const oldCapacity = this._size;
    // Double size if small; else grow by 50%
    const newCapacity =
      oldCapacity + (oldCapacity < 64 ? oldCapacity + 2 : oldCapacity >> 1);
    if (!Number.isSafeInteger(newCapacity)) {
      throw new Error('OOM: new capacity not a safe integer');
    }
    this._queue.length = newCapacity;
  }

  private siftup(k: number, item: T): void {
    if (this._comparator !== null) {
      this.siftupUsingComparator(k, item);
    } else {
      this.siftupComparable(k, item);
    }
  }

  /**
   * siftup of heap
   */
  private siftupUsingComparator(k: number, item: T): void {
    while (k > 0) {
      // find the parent
      const parent = (k - 1) >>> 1;
      const e = this._queue[parent] as T;
      // compare item with it parent, if item's priority less, break siftup and insert
      if (this._comparator!(item, e) >= 0) {
        break;
      }
      // if item's priority more, make it's parent sink and proceed siftup
      this._queue[k] = e;
      k = parent;
    }
    // if k === 0, then we directly insert it
    this._queue[k] = item;
  }

  private siftupComparable(k: number, item: T): void {
    while (k > 0) {
      const parent = (k - 1) >>> 1;
      const e = this._queue[parent] as T;
      if (item.toString().localeCompare(e.toString()) >= 0) {
        break;