Skip to content

Instantly share code, notes, and snippets.

@kristopolous
Created March 10, 2016 01:06
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kristopolous/e0cd136071ef381ea62a to your computer and use it in GitHub Desktop.
Save kristopolous/e0cd136071ef381ea62a to your computer and use it in GitHub Desktop.
A Javascript Priority Queue based on Array
var Priority = (function(){
function sort(pri) {
if(pri.dirty) {
var sorted = pri.sort(function(a, b) {
return 1000000 * (b.priority - a.priority) + 0.0001 * (a.id - b.id);
});
pri.dirty = false;
pri.splice.apply([], [0, 0].concat(sorted));
}
}
function element(what) {
return !what || what.arg;
}
function Priority() {
Object.defineProperty(this, 'id', {
enumerable: false,
writable: true,
value: 0
});
Object.defineProperty(this, 'dirty', {
enumerable: false,
writable: true,
value: false
});
}
Priority.prototype = Object.create(Array.prototype);
Priority.constructor = Priority;
Priority.prototype.push = function(arg, priority) {
Array.prototype.push.call(this, {arg: arg, id: this.id++, priority: priority || 0});
this.dirty = true;
}
Priority.prototype.unshift = function(arg, priority) {
Array.prototype.unshift.call(this, {arg: arg, id: -(this.id++), priority: priority || 0});
this.dirty = true;
}
Priority.prototype.shift = function() {
sort(this);
return element(Array.prototype.shift.call(this));
}
Priority.prototype.pop = function() {
sort(this);
return element(Array.prototype.pop.call(this));
}
return Priority;
})();
@vitkarpov
Copy link

Not a very efficient implementation :)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment