Binary Heap

JavaScript performance comparison

Revision 10 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