Intrinsic Programming by Erik Schulz

Heap sort is similar to selection sort but instead of scanning the entire list for the minimal value it uses a heap to select the minimal value. There is an added step of rebuilding the heap every time the minimal value is removed. Heap sort's worst-case runtime is θ(n log n). In this implementation I use a max heap. Wikipedia on Heap sort.

algorithms.sort.heap = function(array, predicate) {
    var siftDown = function(start, end) {
        var root = start;
        while (root * 2 + 1 <= end) {
            var child = root * 2 + 1;
            if (child < end && predicate(array, child, child + 1)) {
                child++;
            }
            if (predicate(array, root, child)) {
                array.swap(root, child);
                root = child;
            } else {
                return;
            }
        }
    };
    
    var length = array.length;
    
    // turn list into a heap
    for (var start = Math.floor((length - 2) / 2); start >= 0; start--) {
        siftDown(start, length - 1);    
    }

    // remove max value and restore heap property    
    for (var end = length - 1; end > 0; end--) {
        array.swap(end, 0);  
        siftDown(0, end - 1);    
    }
};