Priority Queue

examples.js

var q = new PriorityQueue;

var nums = [ 1, 4, 6, 3, 9 ];
nums.forEach(q.add, q);
nums.forEach(q.add, q);

var outs = [];
while (q.length) outs.push(q.hpop());
console.log(outs);
// [ 9, 9, 6, 6, 4, 4, 3, 3, 1, 1 ]

var jobs = new PriorityQueue(function (job) {
  if (job.critical) return 0;
  return 1;
});

jobs.add({ task: 'email', user_id: 4, critical: false });
jobs.add({ task: 'cache', critical: true });

console.log(jobs.lpop());
// { task: 'cache', critical: true }

priority_queue.js

function PriorityQueue(score) {
  this.score = score || function(x) { return x; };
  this.length = 0;
  this.elements = {};
  this.scores = [];
}

!function (Q) {
  Q.add = function (element) {
    var score = this.score(element);
    if (this.elements[score] == undefined) {
      this.elements[score] = [];
      this.insert(score);
    }
    this.elements[score].push(element);
    this.length ++;
    return this;
  };

  Q.lpop = function () {
    var lowest = this.scores[0];
    var element = this.elements[lowest].shift();
    if (this.elements[lowest].length == 0) {
      delete this.elements[lowest];
      this.scores.shift();
    }
    this.length --;
    return element;
  };

  Q.lpeek = function () {
    var lowest = this.scores[0];
    return this.elements[lowest][0];
  };

  Q.hpop = function () {
    var highest = this.scores[this.scores.length - 1];
    var element = this.elements[highest].shift();
    if (this.elements[highest].length == 0) {
      delete this.elements[highest];
      this.scores.pop();
    }
    this.length --;
    return element;
  };

  Q.hpeek = function () {
    var highest = this.scores[this.scores.length - 1];
    return this.elements[highest][0];
  };

  // private

  Q.insert = function (score) {
    this.scores.splice(this.index(score), 0, score);
  };

  Q.index = function (score) {
    return this.binary(score, Math.floor(this.scores.length / 2))
  };

  Q.binary = function (score, index) {
    if (score < this.scores[index]) {
      if (index == 0 || score > this.scores[index - 1]) {
        return index;
      } else {
        return this.binary(score, index - Math.ceil(index / 2));
      }
    } else if (score > this.scores[index]) {
      var length = this.scores.length;
      if (index == length - 1) {
        return length;
      } else {
        return this.binary(score, index + Math.ceil((length - index) / 2));
      }
    }
  };
}(PriorityQueue.prototype);