priorityqueue

PriorityQueue

An implementation of priority queue in javascript.

Installation

npminstallpriorityqueue
Copy

Example

importPriorityQueuefrom"priorityqueue";

classPoint {
constructor(x, y) {
this.x = x;
this.y = y;
 }
}

constnumericCompare = (a, b) => (a > b ? 1 : a < b ? -1 : 0);

constcomparator = (a, b) => {
constx = numericCompare(a.x, b.x);
consty = numericCompare(a.y, b.y);
returnx ? x : y;
};

constpq = newPriorityQueue({ comparator });

pq.push(newPoint(4, 6));
pq.push(newPoint(2, 3));
pq.push(newPoint(5, 1));
pq.push(newPoint(1, 2));
console.log(pq.pop()); // => {x: 5, y: 1}
console.log(pq.top()); // => {x: 4, y: 6}
pq.push(newPoint(3, 4));
pq.push(newPoint(6, 5));
console.log(pq.length); // => 5
console.log(pq.top()); // => {x: 6, y: 5}
Copy

References

• instance methods
• static methods

Variation

BinaryHeap(default)

Binary heap is a simple and efficient in almost cases.

cons:

• slow with large amount of items(over 10k)
• slow in merge operation especially

PairingHeap

pros:

• super fast in merge operation(constant time)

SkewHeap

pros:

• super fast in merge operation(constant time)

Not to use:

• with sequence completely sorted

Import specific implementation

importPriorityQueuefrom"priorityqueue";
importBinaryHeapfrom"priorityqueue/BinaryHeap";
importPairingHeapfrom"priorityqueue/PairingHeap";
importSkewHeapfrom"priorityqueue/SkewHeap";

console.log(PriorityQueue === BinaryHeap); // => true
Copy

TypeScript users

If your tsconfig specifies moduleResolution: "node" (whether implicitly or explicitly), use priorityqueue/lib/BinaryHeap instead of priorityqueue/BinaryHeap .