Binary Heap

JavaScript performance comparison

Revision 5 of this test case created

Info

a really dumb way (i.e. always sorting the array after every push) make an array behave like a heap

Preparation code

<script>
function numSort(a,b){
if(a < b) return -1;
if(a > b) return 1;
return 0;
}

  // @see http://eloquentjavascript.net/appendix2.html
  function BinaryHeap1(scoreFunction) {
    this.content = [];
    this.scoreFunction = scoreFunction ||
    function(a, b) {
      if (a < b) return -1;
      if (a > b) return 1;
      return 0;
    };
  }

  BinaryHeap1.prototype = {
    push: function(element) {
      // Add the new element to the end of the array.
      this.content.push(element);
      // 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) {
        this.content[0] = end;
        this.sinkDown(0);
      }
      return result;
    },

    remove: function(node) {
      var length = this.content.length;
      // To remove a value, we must search through the array to find
      // it.
      for (var i = 0; i < length; i++) {
        if (this.content[i] != node) continue;
        // 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) break;
        // 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;
        this.bubbleUp(i);
        this.sinkDown(i);
        break;
      }
    },

    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.
        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[n] = this.content[swap];
        this.content[swap] = element;
        n = swap;
      }
    }
  };








  /**
   * can optionally provide a comparison function, a function for a max
   * heap is the default if no comparison function is provided
   *
   * @example
   * var bh = new BinaryHeap();
   * bh.push(5);
   * bh.push(34);
   * bh.push(16);
   * var max = bh.pop(); // 34
   * console.log("Size of heap: %n", bh.size()) // 2
   *
   * @see https://github.com/yckart/BinaryHeap
   */

  function BinaryHeap2(scoreFunction, populate) {
    this.content = populate ? populate.slice(0) : [];

    // default to max heap if comparator is not provided
    this.scoreFunction = scoreFunction ||
    function(a, b) {
      if (a < b) return -1;
      if (a > b) return 1;
      return 0;
    };

    if (this.content.length) this.build();
  }



  /**
   * Create a heap from a random arrangement of data.
   * Building a heap this way is O(n).
   */

  BinaryHeap2.prototype.build = function() {
    var i = Math.floor(this.content.length / 2) - 1;
    while (i--) this.sinkDown(i);
  };


  /**
   * Adds an element to the heap.
   * Building a heap this way is O(n log n).
   *
   * @param {Mixed} element
   */

  BinaryHeap2.prototype.push = function(element) {
    // Add the new element to the end of the array.
    this.content.push(element);

    // Allow it to bubble up.
    this.bubbleUp(this.content.length - 1);
  };


  /**
   * Pops the root off the heap. The root is the element for which
   * the score function returns the minimum score. This is delete-min
   * with O(log n).
   */

  BinaryHeap2.prototype.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) {
      this.content[0] = end;
      this.sinkDown(0);
    }

    return result;
  };



  /**
   * Inspects the root of the heap. This is find-min, O(1).
   */

  BinaryHeap2.prototype.peek = function() {
    return this.content && this.content.length ? this.content[0] : null;
  };



  /**
   * Removes the given element from this heap.
   *
   * @param {Mixed} element
   */

  BinaryHeap2.prototype.remove = function(element) {
    var len = this.content.length;

    // To remove a value, we must search
    // through the array to find it.
    for (var i = 0; i < len; i++) {
      if (this.content[i] === element) {

        // When it is found, the process seen in 'pop' is repeated
        // to fill up the hole.
        var end = this.content.pop();

        if (i !== len - 1) {
          this.content[i] = end;
          if (this.scoreFunction(end) < this.scoreFunction(node)) {
            this.bubbleUp(i);
          } else {
            this.sinkDown(i);
          }
        }
        return;
      }
    }
    throw new Error("Node not found.");
  };



  /**
   * Gets the heap size. I assume JavaScript allows O(n) for this.
   */

  BinaryHeap2.prototype.size = function() {
    return this.content.length;
  };



  /**
   * Bubbles up an element at a given index. This operation is O(log n).
   *
   * @param {Number} n - The number to bubble up
   */

  BinaryHeap2.prototype.bubbleUp = function(n) {
    // Fetch the element that has to be moved.
    var element = this.content[n];

    // 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 (this.scoreFunction(element) < this.scoreFunction(parent)) {

        // Swap the elements if the parent is greater.
        this.content[parentN] = element;
        this.content[n] = parent;

        // Update 'n' to continue at the new position.
        n = parentN;

      } else {
        // Found a parent that is less, no need to move it further.
        break;
      }
    }
  };



  /**
   * Sinks down an element at a given index. This operation is O(log n).
   *
   * @param {Number} n - The number to sink down
   */

  BinaryHeap2.prototype.sinkDown = function(n) {

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

    do {
      // 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;
      }

      // If the element needs to be moved, swap it, and continue.
      if (swap !== null) {
        this.content[n] = this.content[swap];
        this.content[swap] = element;
        n = swap;
      }
    } while (swap !== null);
  };

var numbers = [];
for (var i = 0; i < 200; i++) {
    // May result in the same number being added multiple times:
    numbers.push( Math.floor(Math.random() * 1000) );
}
</script>

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in unknown unknown
Test Ops/sec
BinaryHeap: Marijn Haverbeke
var bh = new BinaryHeap1(),
    i = 0,
    p;
for (; i < 50; i++) bh.push(numbers[i]);
for (p = 0; p < 10; p++) bh.pop();
for (; i < 100; i++) bh.push(numbers[i]);
for (p = 0; p < 40; p++) bh.pop();
for (; i < 200; i++) bh.push(numbers[i]);
for (p = 0; p < 150; p++) bh.pop();
pending…
BinaryHeap: Yannick Albert
var bh = new BinaryHeap2(),
    i = 0,
    p;
for (; i < 50; i++) bh.push(numbers[i]);
for (p = 0; p < 10; p++) bh.pop();
for (; i < 100; i++) bh.push(numbers[i]);
for (p = 0; p < 40; p++) bh.pop();
for (; i < 200; i++) bh.push(numbers[i]);
for (p = 0; p < 150; p++) bh.pop();
pending…
Test Sort
var bh = [],
    i = 0,
    p;
for (; i < 50; i++) {
bh.push(numbers[i]);
bh.sort(numSort);
}
for (p = 0; p < 10; p++) bh.pop();
for (; i < 100; i++) {
bh.push(numbers[i]);
bh.sort(numSort);
}
for (p = 0; p < 40; p++) bh.pop();
for (; i < 200; i++) {
bh.push(numbers[i]);
bh.sort(numSort);
}
for (p = 0; p < 150; p++) bh.pop();
pending…

Compare results of other browsers

Revisions

You can edit these tests or add even more tests to this page by appending /edit to the URL. Here’s a list of current revisions for this page:

0 comments

Add a comment