Cartesian Tree Sort

Thursday, June 24, 2010 by gradbot

Cartesian tree sort solves heap sort's problem of not taking advantage of partially sorted data by building a Cartesian tree. This tree is then traversed pre-prder inserting nodes into a priority queue. The nodes are removed from the priority queue as they are being inserted. Since the Cartesian tree is also a heap, nodes are not removed out of order. In the case of partially sorted data, the Cartesian tree degrades into an unbalanced tree resembling a linked list. Since there is only one element per row, the priority queue pushes and pops the same element without doing any comparisons.

This has θ(n log n) worse case running time and θ(n) running time for sorted data. Cartesian tree sort does require extra space for the tree and priority queue. Wikipedia on Cartesian tree sort.

This flattened Cartesian tree graph has a x-axis of the element index and a y-axis of the nodes depth. The root is the topmost dot. Cartesian trees can be built in linear time and will return the original data in order if the tree is traversed in-order.



algorithms.sort.cartesian_tree = function(array, predicate) {
    var queue = algorithms.queue.priority(function(a, b) {
        return predicate(a.value, b.value);
    });
    
    var length = array.length;
    if (length <= 1) return;
    
    var root = {"parent": null, "value": array[0], "left": null, "right": null};
    var last = root;
    
    for (var i = 1; i < length; i++) {
        while(last && predicate(last.value, array[i])) {
            last = last.parent;
        }
        if (last) {
            last.right = {"parent": last, "value": array[i], "left": last.right, "right": null};
            last = last.right;
        } else {
            root = {"parent": null, "value": array[i], "left": root, "right": null};
            last = root;
        }
    }
    
    queue.add(root);
    array = [];
    while(!queue.empty()) {
        var node = queue.remove();
        
        array.push(node.value);
        
        if (node.left) {
            queue.add(node.left);
        }
        
        if (node.right) {
            queue.add(node.right);
        }
    }
};

Filed under , , , having  

0 comments: