Priority Queue & Heap Sort

Thursday, June 10, 2010 by gradbot

A heap implementation of priority queue is very similar to heap sort and can easily be turned into one. The difference implementation wise is that the queue doesn't know the final heap size so it has to build the heap from the ground up. This requires finding parent nodes in the heap and not just child nodes. Performance is nearly identical except the queue requires extra N space. Both of these heap implementations don't take advantage of partially sorted list.



algorithms.queue.priority = function(predicate) {
    var siftDown = function(array, 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 siftUp = function(array, start, end) {
        var child = end;
        while (child > start) {
            var parent = Math.floor((child - 1) / 2);
            if (predicate(array, parent, child)) {
                array.swap(parent, child);
                child = parent;
            } else {
                return;
            }
        }
    };
    var that = {
        heap: [],
        add: function(value) {
            that.heap.push(value);
            siftUp(that.heap, 0, that.heap.length - 1);
        },
        remove: function() {
            that.heap.swap(0, that.heap.length - 1);
            siftDown(that.heap, 0, that.heap.length - 2);
            return that.heap.pop();
        }
    };
    return that;
};

algorithms.sort.heap_priority = function(array, predicate) {
    var queue = algorithms.queue.priority(predicate);
    var length = array.length;

    // turn list into a heap
    for (var i = 0; i < length; i++) {
        queue.add(array[i]);
    }

    // remove max value and restore heap property  
    for (var i = 0; i < length; i++) {
        array[i] = queue.remove();
    }   
};

Filed under , , , having  

0 comments: