binary heap and priority queue structures

binary_heap.js

/*
 * Binary Heap
 *
 * This is a heap which is built on top of a binary tree. The binary tree can
 * be built using a regular array and some arithmetic to find the array indicies
 * of a particular node's children.
 *
 * The Binary Heap is a 'complete tree', meaning that all levels of the tree are
 * completely filled before going deeper. The levels of the tree are filled from
 * left to right.
 *
 * The Binary Heap is also satisfies the 'heap property', that is, it is heap 
 * ordered - which means that every node is either always greater or less than 
 * its children. One could implement a 'binary-min' tree which which would mean
 * that all nodes are less than or equal to their children. Or conversely a
 * 'binary-max' tree would mean that all nodes are greater than or equal to
 * their children.
 *
 * What is this good for:
 * - Implementing Priority Queues
 *
 * References:
 * http://eloquentjavascript.net/appendix2.html
 * http://opendatastructures.org/versions/edition-0.1e/ods-java/10_1_BinaryHeap_Implicit_Bi.html
 * http://en.wikipedia.org/wiki/Binary_heap
 */

function BinaryHeap(_compareFn) {
  // nodes are stored in a regular array
  this.nodes = [];

  // compare the values of two nodes at indexA and indexB
  this.compareFn = _compareFn || function(nodeA, nodeB) {
    if(nodeA > nodeB) return 1;
    if(nodeA < nodeB) return -1;
    return 0;
  };
}

/**
 * Lookup left child index
 * @param {Number} i - parent index
 * @returns {Number} - index for left child node
 */
BinaryHeap.prototype.left = function(i) {
  return 2 * i + 1;
};

/**
 * Lookup right child index
 * @param {Number} i - parent index
 * @returns {Number} - index for right child node
 */
BinaryHeap.prototype.right = function(i) {
  return 2 * i + 2;
};

/**
 * Lookup parent node index
 * @param {Number} i - child index
 * @returns {Number} - index for parent node
 */
BinaryHeap.prototype.parent = function(i) {
  return Math.floor((i - 1) / 2);
};

/**
 * Insert new node to heap. Add to the end of the array then "bubble up"
 * @param {Object} node - object to serve as node
 * @returns {BinaryHeap} this
 */
BinaryHeap.prototype.add = function(node) {
  this.nodes.push(node); // add node to the end of the array
  this.bubbleUp(this.nodes.length - 1);
  return this;
};

/**
 * Swap two nodes in the heap at indexA and indexB
 * @param {Number} indexA
 * @param {Number} indexB
 * @returns {BinaryHeap} this
 */
BinaryHeap.prototype.swapNodes = function(indexA, indexB) {
  var nodeA = this.nodes[indexA];
  var nodeB = this.nodes[indexB];
  this.nodes[indexA] = nodeB;
  this.nodes[indexB] = nodeA;
  return this;
};

/**
 * Reorders the nodes in the heap to ensure that the node at index i is less
 * than its parents value. This is done by comparing the last node of the heap
 * with its parents and swapping it until it is not less than its parent.
 * @param {Number} i - index of the node to bubble up
 * @returns {BinaryHeap} this
 */
BinaryHeap.prototype.bubbleUp = function(i) {
  pi = this.parent(i);
  // loop until node at index i is <= it's parent node
  while(this.compare(i, pi) < 0){
    this.swapNodes(i, pi);
    i = pi;
    pi = this.parent(i);
  }
  return this;
};

/**
 * Returns the first node in the heap. This will be the smallest value node in
 * the heap. Resort the array by "bubbling down" to make sure the first node in
 * the heap is again the smallest value.
 * @returns {Object} - node
 */
BinaryHeap.prototype.remove = function() {
  var rootNode = this.nodes.shift();
  this.bubbleDown();
  return rootNode;
};

/**
 * Apply this.compareFn to nodes at indexA and indexB
 * @param {Number} indexA
 * @param {Number} indexB
 * @returns {Number} - result of comparision function (-1, 0, 1)
 */
BinaryHeap.prototype.compare = function(indexA, indexB) {
  var nodeA = this.nodes[indexA];
  var nodeB = this.nodes[indexB];
  return this.compareFn(nodeA, nodeB);
};

/**
 * Reorder the heap. This is done by taking the last node on the heap
 * and putting it at the front, then push it through the array swapping with
 * greater values until it is less than its parents.
 * @returns {BinaryHeap} this
 */
BinaryHeap.prototype.bubbleDown = function() {
  if(this.size() < 1) return; // 
  // take last node in array off and put at the front of the array
  var lastNode = this.nodes.pop();
  this.nodes.unshift(lastNode);

  var i = 0;
  var l = this.left(0);  // left child index
  var r = this.right(0); // right child index

  // while the current node's value is greater than its children
  while(this.compare(i, l) > 0 || this.compare(i, r) > 0){

    if(this.compare(l, r) < 0){
      // left child is less than right
      this.swapNodes(i, l);
      i = l;
    }else{
      // right child is less than left
      this.swapNodes(i, r);
      i = r;
    }
    l = this.left(i);
    r = this.right(i);
  }
  return this;
};

/**
 * Size of the heap.
 * @returns {Number} - count of the nodes in the heap
 */
BinaryHeap.prototype.size = function() {
  return this.nodes.length;
};

module.exports = BinaryHeap;

priority_queue.js

/*
 * Priority Queue
 *
 * Similar to an ordinary FIFO queue, but each element in the queue can be
 * assigned a priority which determines the queue's ordering. The PQ is typiclly
 * built on top of a Binary Heap (as it is here) because it can guarantee that
 * the first element to be pulled off the queue will be of the highest priority
 * and is fast at achieving this ordering.
 *
 * Note: because this PQ is built on a BinaryHeap an important part of this
 * implementation is that we must provide the BinaryHeap with a sort function
 * that knows how to compare the elements we are adding to the queue.
 *
 * What this is good for:
 * - Can be used to sort elements by priority value
 * - Scheduling events
 * -
 *
 * References:
 * http://en.wikipedia.org/wiki/Priority_queue
 */

var BinaryHeap = require('./BinaryHeap');

function PriorityQueue() {
  var compareFn = function(nodeA, nodeB) {
    if (nodeA && nodeB) {
      if (nodeA.priority > nodeB.priority) return 1;
      if (nodeA.priority < nodeB.priority) return -1;
    }
    return 0;
  };
  this.queue = new BinaryHeap(compareFn);
}

/**
 * Add an element to the queue with a priority.
 * @param {*} element - something to queue
 * @param {Number} priority
 * @returns {PriorityQueue} this
 */
PriorityQueue.prototype.enqueue = function(element, priority) {
  this.queue.add({element: element, priority: priority});
  return this;
};

/**
 * Remove element with highest priority from the queue.
 * @returns {*|undefined} - element || undefined if queue is empty.
 */
PriorityQueue.prototype.dequeue = function() {
  if (this.isEmpty()) { 
    return undefined;
  } else {
    var highestPriority = this.queue.remove();
    return highestPriority.element;
  }
};

/**
 * Check whether the queue is empty.
 * @returns {Boolean}
 */
PriorityQueue.prototype.isEmpty = function(){ 
  return this.queue.length === 0;
};

/**
 * Get size of the queue.
 * @returns {Number}
 */
PriorityQueue.prototype.size = function(){ 
  return this.queue.size();
};

module.exports = PriorityQueue;