A priority queue with your own comparator

A request scheduler sends the user-visible fetch before the prefetch; a notification centre shows the critical alert above the chatty one. Both need a queue ordered by priority rather than arrival, with the rule supplied by the caller.

Implement a PriorityQueue class. new PriorityQueue(compare) takes an optional comparator with the same contract as Array#sort: compare(a, b) returns a negative number when a should come out before b, a positive number when it should come out after, and zero when they are equally urgent. When no comparator is given, default to ascending numeric order, (a, b) => a - b. push(item) inserts an item and returns the new size. pop() removes and returns the item that comes first under the comparator, or undefined when the queue is empty. peek() returns that item without removing it, or undefined when empty. size() returns how many items are held, and isEmpty() returns true when it holds none.

The order among items the comparator calls equal is not defined, so do not rely on it.

What it has to do

• With no comparator, pop() returns numbers in ascending order.
• A supplied comparator decides the order, including over objects.
• pop() and peek() return undefined on an empty queue.
• push returns the new size and pushes may be interleaved with pops.
• Do not sort the whole collection on every push.

Your workspace