Binary Heap

JavaScript performance comparison

Revision 3 of this test case created by jlgrall

Info

Fixed: better times the push and pop operations. (Instead of Binary Heap creation time). (See comment on version 2)

Preparation code

<script>
  // @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);
  };






/**
 * @author Derrick Burns
 */



binaryHeap = function (comparisonFunction) {
    this.cmp = comparisonFunction ||
    function(a, b) {
      if (a < b) return -1;
      if (a > b) return 1;
      return 0;
    };;
};

binaryHeap.prototype = {
    content: [],

    toArray: function( ) {
        var r = "[";
        for( var i=0; i!= this.content.length; i++ )  {
            r = r + this.content[i].toString();
            r = r + ", ";
        }
        r = r + "]";
        return r;
    },
       
    push: function (element) {
        // Add the new element to the end of the array.
        this.content.push(element);
        // Allow it to sink down.
        this.sinkDown(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 bubble up.
        if (this.content.length > 0) {
            this.content[0] = end;
            this.bubbleUp(0);
        }
        return result;
    },

    remove: function (node) {
        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] === node) {
                // When it is found, the process seen in 'pop' is repeated
                // to fill up the hole.
                var end = this.content.pop();
                if (i !== this.content.length - 1) {
                    this.content[i] = end;
                    this.bubbleUp(i);
                }
                return;
            }
        }
        throw new Error("Node not found.");
    },

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

    sinkDown: function (n) {
        // Fetch the element that has to be sunk.
        var element = this.content[n];
        // When at 0, an element can not sink 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];
            // Swap the elements if the parent is greater.
            if (this.cmp(element, parent) < 0) {
                this.content[parentN] = element;
                this.content[n] = parent;
                // Update 'n' to continue at the new position.
                n = parentN;
            }
            // Found a parent that is less, no need to sink any further.
            else {
                break;
            }
        }
    },

    bubbleUp: function (n) {
        // Look up the target element.
        var length = this.content.length,
        element = this.content[n];

        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
                var child1 = this.content[child1N];
                // If it is less than our element's, we need to swap.
                if (this.cmp(child1, element) < 0) {
                    swap = child1N;
                }
            }
            // Do the same checks for the other child.
            if (child2N < length) {
                var child2 = this.content[child2N];
                if (this.cmp(child2, (swap === null ? element: child1)) < 0) {
                    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;
            }
            // Otherwise, we are done.
            else {
                break;
            }
        }
    }
};

BinaryHeap3 = function(comparisonFunction) {
    var b = new binaryHeap(comparisonFunction);
    return {
        toArray: function() { return b.toArray(); },
        push:    function(elem) { return b.push(elem); },
        pop:     function() { return b.pop(); },
        remove:  function(elem) { return b.remove(elem); },
        size:    function() { return b.size(); }
    }
}();

var bh1 = new BinaryHeap1(),
    bh2 = new BinaryHeap2(),
    bh3 = BinaryHeap3;

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 = bh1,
    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 = bh2,
    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: Derrick Burns
var bh = bh3,
    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…

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