heap.js

function BinaryHeap(scoreFunction){
  this.content = [];
  this.scoreFunction = scoreFunction;
}

BinaryHeap.prototype = {
  push: function(element) {
    // Add the new element to the end of the array.
    this.content.push(element);
    element.__heapIdx = this.content.length - 1;
    // Allow it to bubble up.
    this.bubbleUp(this.content.length - 1);
  },

  pop: function() {
    // Store the first element so we can return it later.
    var result = this.content[0];
    // Get the element at the end of the array.
    var end = this.content.pop();
    // If there are any elements left, put the end element at the
    // start, and let it sink down.
    if (this.content.length > 0) {
      end.__heapIdx = 0;
      this.content[0] = end;
      this.sinkDown(0);
    }
    return result;
  },

  remove: function(node) {
    var length = this.content.length;
    var i = node.__heapIdx;
    // When it is found, the process seen in 'pop' is repeated
    // to fill up the hole.
    var end = this.content.pop();
    // If the element we popped was the one we needed to remove,
    // we're done.
    if (i == length - 1) return;
    // Otherwise, we replace the removed element with the popped
    // one, and allow it to float up or sink down as appropriate.
    this.content[i] = end;
    end.__heapIdx = i;
    this.bubbleUp(i);
    this.sinkDown(i);
  },

  size: function() {
    return this.content.length;
  },

  bubbleUp: function(n) {
    // Fetch the element that has to be moved.
    var element = this.content[n], score = this.scoreFunction(element);
    // When at 0, an element can not go up any further.
    while (n > 0) {
      // Compute the parent element's index, and fetch it.
      var parentN = Math.floor((n + 1) / 2) - 1,
      parent = this.content[parentN];
      // If the parent has a lesser score, things are in order and we
      // are done.
      if (score >= this.scoreFunction(parent))
        break;

      // Otherwise, swap the parent with the current element and
      // continue.
      element.__heapIdx = parentN;
      parent.__heapIdx = n;
      this.content[parentN] = element;
      this.content[n] = parent;
      n = parentN;
    }
  },

  sinkDown: function(n) {
    // Look up the target element and its score.
    var length = this.content.length,
    element = this.content[n],
    elemScore = this.scoreFunction(element);

    while(true) {
      // Compute the indices of the child elements.
      var child2N = (n + 1) * 2, child1N = child2N - 1;
      // This is used to store the new position of the element,
      // if any.
      var swap = null;
      // If the first child exists (is inside the array)...
      if (child1N < length) {
        // Look it up and compute its score.
        var child1 = this.content[child1N],
        child1Score = this.scoreFunction(child1);
        // If the score is less than our element's, we need to swap.
        if (child1Score < elemScore)
          swap = child1N;
      }
      // Do the same checks for the other child.
      if (child2N < length) {
        var child2 = this.content[child2N],
        child2Score = this.scoreFunction(child2);
        if (child2Score < (swap == null ? elemScore : child1Score))
          swap = child2N;
      }

      // No need to swap further, we are done.
      if (swap == null) break;

      // Otherwise, swap and continue.
      this.content[swap].__heapIdx = n;
      element.__heapIdx = swap;
      this.content[n] = this.content[swap];
      this.content[swap] = element;
      n = swap;
    }
  }, 

  decreaseKey: function(node) {
    var i = node.__heapIdx;

    var elem = this.content[i];
    var score = this.scoreFunction(elem);
    var parentIdx = Math.floor((i - 1)  / 2);
    var parent = this.content[parentIdx];

    while (parentIdx >= 0) {
      if(this.scoreFunction(parent) <= score) {
        break;
      }
      parent.__heapIdx = i;
      elem.__heapIdx = parentIdx;
      this.content[i] = parent;
      this.content[parentIdx] = elem;
      i = parent;      
    }
  }
};