A heap-based priority queue in JavaScript

PriorityQueue.js

// PriorityQueue.js MIT License © 2014 James Abney http://github.com/jabney
(function(ex) {
'use strict';

// ---------------------------------------------------------------
// PriorityQueue Constructor
// A heap-based priority queue.
// ---------------------------------------------------------------
ex.PriorityQueue = function PriorityQueue(compare) {
  var compare = compare || function(a, b) { return a < b; },
  heap = [],
  slice = Array.prototype.slice;

  // Initialize the priority queue with an array of items.
  this.init = function(items) {
    if (heap.length) heap = [];
    this.insert.apply(null, items);
    return this;
  };

  // Insert one or more items into the priority queue.
  this.insert = function() {
    slice.call(arguments, 0).forEach(function(item) {
      heap.push(item);
      float(heap.length - 1);
    });
    return this;
  };

  // Remove and return the next queue element.
  this.remove = function() {
    var head = null, last;
    if (heap.length) {
      head = heap[0];
      last = heap.length - 1;
      swap(0, last);
      heap.splice(last, 1);
      sink(0);
    }
    return head;
  };

  // Clear all items from the queue.
  this.clear = function() {
    heap = [];
    return this;
  };

  // Return the top item without modifying the queue.
  this.peek = function() {
    return heap[0];
  };

  // Return the number of items in the queue.
  this.size = function() {
    return heap.length;
  };

  // Return true if the queue is empty.
  this.empty = function() {
    return !heap.length;
  };

  // Sink an item from the top down to heap order.
  function sink(h) {
    var left = 2*h+1, right = 2*h+2, child = left;
    if (left < heap.length) {
      right < heap.length && compare(heap[right], heap[left]) && child++;
      if (compare(heap[child], heap[h])) {
        swap(h, child);
        sink(child);
      }
    }
  }

  // Float an item from the bottom up to heap order.
  function float(h) {
    var parent = Math.floor((h-1)/2);
    if (parent >= 0 && compare(heap[h], heap[parent])) {
        swap(h, parent);
        float(parent);
    }
  }

  // Swap two heap elements by index.
  function swap(i, j) {
    var tmp = heap[i];
    heap[i] = heap[j];
    heap[j] = tmp;
  }
}
})(typeof exports !== 'undefined' && exports || this);


//
// Tests
//

// Generate an array of integers [0, n).
function varArray(n) {
  var i, out = [];
  for(i = 0; i < n; i++)
    out.push(i);
  return out;
}

// Shuffle an array so that the positions of its values are random.
function shuffle(a) {
  var i, r, tmp, len = a.length;
  for (i = 0; i < len; i++) {
    r = i + Math.floor((len - i) * Math.random());
    tmp = a[i];
    a[i] = a[r];
    a[r] = tmp;
  }
  return a;
}

// Generate an error if queue items are removed in the wrong order.
function verifyOrder(pq, compare) {
  var out = [], last = pq.peek(), size = pq.size();
  while (pq.size()) {
    if (!compare(last, item = pq.remove()))
      console.error('inconsistent queue order');
    last = item;
    out.push(item);
  }
  if (size !== out.length)
    console.error('size mismatch:');
  return out;
}

// Test using numbers.

(function(PriorityQueue) {
  var a = varArray(20), pq;
  // Less
  shuffle(a);
  pq = new PriorityQueue().init(a);
  console.log('less queue order: (numbers)', verifyOrder(pq,
    function(a, b) { return a <= b; }));
  // Greater
  shuffle(a);
  pq = new PriorityQueue(function(a, b) { return a > b; }).init(a);
  console.log('greater queue order (numbers):', verifyOrder(pq, 
    function(a, b) { return a >= b; }));
})(window.PriorityQueue);

// Test using strings.

(function(PriorityQueue) {
  var pq, a = ['cat', 'dog', 'bat', 'emu', 'pig', 'hen', 'hog', 
    'yak', 'cow', 'fox', 'jay', 'owl', 'rat', 'ram', 'moa'];
  // Less
  shuffle(a);
  pq = new PriorityQueue(function(a, b) { return a < b; }).init(a);
  console.log('less queue order (strings):', verifyOrder(pq,
    function(a, b) { return a <= b; }));
  // Greater
  shuffle(a);
  pq = new PriorityQueue(function(a, b) { return a > b; })
    .init(a);
  console.log('less queue order (strings):', verifyOrder(pq,
    function(a, b) { return a >= b; }));
})(window.PriorityQueue);

// Test with vectors and a custom compare function (a < b).

(function(PriorityQueue) {
  // Return the magnitude of a vector.
  function mag() {
    return Math.sqrt(this.x*this.x + this.y*this.y);
  }
  var
  v1 = {x: 1, y: 3, mag: mag},
  v2 = {x: 2, y: 1, mag: mag},
  v3 = {x: 3, y: 4, mag: mag},
  v4 = {x: 2, y: 4, mag: mag},
  vectors = [v1, v2, v3, v4], pq;
  // Less
  shuffle(vectors);
  pq = new PriorityQueue(function(a, b) {
    return a.mag() < b.mag(); }).init(vectors);
  console.log('less queue order (vector magnitude):', verifyOrder(pq,
    function(a, b) { return a.mag() <= b.mag(); })
      .map(function(item) { return item.mag().toPrecision(4); }));
  // Greater
  shuffle(vectors);
  pq = new PriorityQueue(function(a, b) {
    return a.mag() > b.mag(); }).init(vectors);
  console.log('less queue order (vector magnitude):', verifyOrder(pq,
    function(a, b) { return a.mag() >= b.mag(); })
      .map(function(item) { return item.mag().toPrecision(4); }));
})(window.PriorityQueue);