A stable heap-based priority queue in JavaScript
In a priority queue, you can...
- 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
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 usageYou 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 0or
varx=newStablePriorityQueue(function(a,b){returna.energy-b.energy;});[{name: 'player',energy: 10},{name: 'monster1',energy: 10},{name: 'monster2',energy: 10},{name: 'monster3',energy: 10}].forEach(function(o){x.add(o);})while(!x.isEmpty()){console.log(x.poll());}// will output://{ name: 'player', energy: 10 }//{ name: 'monster1', energy: 10 }//{ name: 'monster2', energy: 10 }//{ name: 'monster3', energy: 10 }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 stablepriorityqueue
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.
Using node.js (npm), you can test the code as follows...
$ npm install mocha
$ npm test
If you like this library, you might also like