You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
query or remove (poll) the smallest element quickly
insert elements quickly
In practice, "quickly" often means in logarithmic time (O(log n)).
A heap can be used to implement a priority queue.
StablePriorityQueue is an attempt to implement a priority queue
in JavaScript that is stable. That is, when equal values are inserted, it will always poll the oldest of the equal values.
License: Apache License 2.0
Usage
varx=newStablePriorityQueue();x.add(1);x.add(0);x.add(5);x.add(4);x.add(3);x.peek();// should return 0, leaves x unchangedx.size;// should return 5, leaves x unchangedwhile(!x.isEmpty()){console.log(x.poll());}// will print 0 1 3 4 5x.trim();// (optional) optimizes memory usage
You can also provide the constructor with a comparator function.
varx=newStablePriorityQueue(function(a,b){returnb-a});x.add(1);x.add(0);x.add(5);x.add(4);x.add(3);while(!x.isEmpty()){console.log(x.poll());}// will print 5 4 3 1 0
If you are using node.js, you need to import the module:
varStablePriorityQueue=require("stablepriorityqueue");varb=newStablePriorityQueue();// initially emptyb.add(1);// add the value "1"
npm install
$ npm install stablepriorityqueue
Computational complexity
The function calls "add" and "poll" have logarithmic complexity with respect
to the size of the data structure (attribute size). Looking at the top value
is a constant time operation.
Testing
Using node.js (npm), you can test the code as follows...