Heap.js

/**
 * A simple Binary Heap implementation for JS
 * https://en.wikipedia.org/wiki/Binary_heap
 *
 * Useful improvements would support a comparsion function
 * and allow object removal by reference.
 */

function Heap () {
  var _arr = [];

  // === Private ================================= //

  function childIndicesOf (n) {
    return [((2 * n) + 1), ((2 * n) + 2)];
  }

  function favoredChildIndexOf (n) {
    var childAIndex = (2 * n) + 1;
    var childBIndex = (2 * n) + 2;
    return (_arr[childAIndex] > _arr[childBIndex]) ? childAIndex : childBIndex;
  }

  function parentIndexOf (n) {
    return Math.floor((n - 1) / 2);
  }

  function bubble (n) {
    var item = _arr[n];
    var parentIndex = parentIndexOf(n);
    var parent = _arr[parentIndex];
    if (item > parent) {
      _arr[n] = parent;
      _arr[parentIndex] = item;
      bubble(parentIndex);
      return true;
    }
    return false;
  }

  function sink (n) {
    var item = _arr[n];
    var favoredChildIndex = favoredChildIndexOf(n);
    var favoredChild = _arr[favoredChildIndex];
    if (item < favoredChild) {
      _arr[n] = favoredChild;
      _arr[favoredChildIndex] = item;
      sink(favoredChildIndex);
      return true;
    }
    return false;
  }

  // === Public ================================== //

  this.insert = function (item) {
    _arr.push(item);
    bubble(_arr.length - 1);
  }

  this.removeAt = function (n) {
    if (n === _arr.length - 1) {
      _arr.pop();
    } else {
      _arr[n] = _arr.pop();
      bubble(n) || sink(n);
    }
  }

  this.peek = function () {
    return _arr[0];
  }

  this.pop = function () {
    var root = _arr[0];
    this.removeAt(0);
    return root;
  }
}