Binary Heap

JavaScript performance comparison

Revision 9 of this test case created

Info

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

Preparation code

<script>
/**
 * @author jonboy
 */


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

BinaryHeap4 = function(scoreFunction) {
        this.content = [];
        // default to max heap if comparator is not provided
        this.scoreFunction = scoreFunction ||
        function(a, b) {
                return (b - a)l
        };
};

BinaryHeap4.prototype = {
        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) {
                        this.content[0] = end;
                        this.bubbleUp(0);
                }
                return result;
        },
        remove : function(node) {
                var i = this.content.indexOf(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;

                        if (this.scoreFunction(end) < this.scoreFunction(node)) {
                                this.sinkDown(i);
                        } else {
                                this.bubbleUp(i);
                        }
                }
        },
        size : function() {
                return this.content.length;
        },
        rescoreElement : function(node) {
                this.sinkDown(this.content.indexOf(node));
        },
        sinkDown : function(n) {
                // Fetch the element that has to be sunk.
                var element = this.content[n];
                var parentN, parent;

                // When at 0, an element can not sink any further.
                while (n > 0) {

                        // Compute the parent element's index, and fetch it.
                        parentN = ((n + 1) >> 1) - 1
                        parent = this.content[parentN];
                        // Swap the elements if the parent is greater.
                        if (this.scoreFunction(element) < this.scoreFunction(parent)) {
                                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 and its score.
                var length = this.content.length, element = this.content[n], elemScore = this.scoreFunction(element);
                var swap, child1, child2, child1N, child2N;

                do {
                        // Compute the indices of the child elements.
                        child2N = (n + 1) << 1
                        child1N = child2N - 1;
                        // This is used to store the new position of the element,
                        // if any.
                        swap = null;
                        // If the first child exists (is inside the array)...
                        if (child1N < length) {
                                // Look it up and compute its score.
                                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) {
                                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 bh1 = new BinaryHeap1(), bh2 = new BinaryHeap2(), bh3 = BinaryHeap3, bh4 = new BinaryHeap4();

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