# Binary Heap

## JavaScript performance comparison

Revision 7 of this test case created

## Info

a more typical way to make an array behave like a heap; we also make more frequent sorts (simulating more frequent need of the sorted data)

## 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;for (var grp = 0; grp < 40; grp++) {  for (i = 0; i < 5; i++) bh.push(numbers[i * grp]);  bh.pop();  bh.pop();}``
pending…
BinaryHeap: Yannick Albert
``var bh = new BinaryHeap2(),  i = 0;for (var grp = 0; grp < 40; grp++) {  for (i = 0; i < 5; i++) bh.push(numbers[i * grp]);  bh.pop();  bh.pop();}``
pending…
Test Sort
``var bh = [],  i = 0;for (var grp = 0; grp < 40; grp++) {  for (i = 0; i < 5; i++) bh.push(numbers[i * grp]);  bh.sort(numSort);  bh.pop();  bh.pop();}``
pending…

## 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:

Comment form temporarily disabled.