collections.js

export class PriorityQueue {
  constructor() {
    this._vertices = [];
  }

  get size() {
    return this._vertices.length;
  }

  insert(element, measure) {
    let index = this._vertices.length;
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      const parent = this._vertices[parentIndex];
      if (parent.measure < measure) {
        break;
      }
      this._vertices[index] = parent;
      index = parentIndex;
    }
    this._vertices[index] = {
      element,
      measure,
    };
  }

  remove() {
    console.assert(this._vertices.length > 0, 'Cannot remove an element from an empty priority queue');
    const result = this._vertices[0].element;
    const vertex = this._vertices[this._vertices.length - 1];
    for (let index = 0; ;) {
      this._vertices[index] = vertex;
      let swapIndex = index;
      for (const candidateIndex of [2 * index + 1, 2 * index + 2]) {
        if (candidateIndex < this._vertices.length - 1 &&
            this._vertices[candidateIndex].measure < this._vertices[swapIndex].measure) {
          swapIndex = candidateIndex;
        }
      }
      if (swapIndex === index) {
        this._vertices[index] = vertex;
        this._vertices.pop();
        return result;
      }
      this._vertices[index] = this._vertices[swapIndex];
      index = swapIndex;
    }
  }
}