PriorityQueue.js uses a binary heap to ensure the highest priority item is always available to dequeue, and sorts on enqueue. A dynamically resizing Array can be used to model the binary heap, for a simpler and more efficient implementation.

PriorityQueue.js

/**
 * For compare function return:
 * - Less than zero: item1 has higher priority than item2.
 * - Zero: same.
 * - Greater than zero: item1 has lower priority than item2.
 */
export type CompareFunction<T> = (item1: T, item2: T) => number;

export class PriorityQueue<T> {
  _items: Array<T>;
  _compare: CompareFunction<T>;

  constructor(compare: CompareFunction<T>): void {
    this._items = [];
    this._compare = compare;
  }

  enqueue(item: T): void {
    let child = this._items.push(item) - 1;
    // Satisfy heap by recursively comparing to parent node.
    while (child !== 0) {
      const parent = (child - 1) >>> 1;
      if (this._priority(parent, child) === parent) {
        break;
      }
      this._swap(parent, child);
      child = parent;
    }
  }

  dequeue(): ?T {
    const length = this._items.length;
    if (length !== 0) {
      this._swap(0, length - 1);
      const result = this._items.pop();
      // Satisfy heap by recursively comparing to child nodes.
      let parent = 0;
      while (true) {
        const child = (parent << 1) + 1;
        const high = this._priority(this._priority(parent, child), child + 1);
        if (high === parent) {
          break;
        }
        this._swap(parent, high);
        parent = high;
      }
      return result;
    }
  }

  _priority(parent: number, child: number): number {
    return child < this._items.length &&
      this._compare(this._items[parent], this._items[child]) > 0
      ? child
      : parent;
  }

  _swap(parent: number, child: number): void {
    const temp = this._items[parent];
    this._items[parent] = this._items[child];
    this._items[child] = temp;
  }
}

Includes type definitions which work in both TypeScript and Flow.

By the way, two common methods Queues often have are length and peek. The additions of which become trivial by using an Array as a binary heap:

get length(): number {
  return this._items.length;
}

peek(): ?T {
  return this._items[0];
}