PriorityQueue.js

class PriorityQueue {
  constructor(compare = (a, z) => a - z) {
    this.data = [];
    this.compare = compare;
  }
  get length() {
    return this.data.length;
  }
  push(item) {
    this.data.push(item);
    this._up(this.length - 1);
  }
  pop() {
    if (this.length <= 1) return this.data.pop();
    const top = this.data[0];
    this.data[0] = this.data.pop();
    this._down(0);
    return top;
  }
  peek() {
    return this.data[0];
  }
  _up(pos) {
    const { data, compare } = this;
    const item = data[pos];
    while (pos > 0) {
      const parent = (pos - 1) >> 1;
      const parentItem = data[parent];
      if (compare(item, parentItem) >= 0) break;
      data[pos] = parentItem;
      pos = parent;
    }
    data[pos] = item;
  }
  _down(pos) {
    const { data, compare } = this;
    const half = this.length >> 1;
    const item = data[pos];
    while (pos < half) {
      const left = (pos << 1) + 1;
      const right = left + 1;
      const child =
        right < this.length && compare(data[right], data[left]) < 0
          ? right
          : left;
      if (compare(data[child], item) >= 0) break;
      data[pos] = data[child];
      pos = child;
    }
    data[pos] = item;
  }
}