JavaScript binary heap with merge support

gistfile1.js

var BinaryHeap = function BinaryHeap(scoreFunction, populate){
    this.content = (populate ? populate.slice(0) : []);
    this.scoreFunction = scoreFunction;
    
    if (this.content.length) {
        this.build();
    }
}

BinaryHeap.prototype = {
    
    /**
     * Create a heap from a random arrangement of data.
     * Building a heap this way is O(n).
     */
    build: function() {
        var lastNonLeaf = Math.floor(this.content.length / 2) - 1;
        for (var i = lastNonLeaf; i >= 0; i--) {
            this.sinkDown(i);
        }
    },
    
    /**
     * Adds an element to the heap. 
     * Building a heap this way is O(n log n).
     */
    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).
     */
    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).
     */
    peek: function() {
        return (this.content && this.content.length ? this.content[0] : null);
    },

    /**
     * Removes the given element from this heap.
     */
    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.
     */
    size: function() {
        return this.content.length;
    },

    /**
     * Bubbles up an element at a given index. This operation is O(log n).
     */
    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).
     */
    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);
    }
};