Cartesian Tree Sort - Skew Heap

Monday, June 28, 2010 by gradbot

Since any heap tree, including Cartesian trees, degrade into sorted linked list when they are fully unbalanced it makes sense to try and unbalance the Cartesian tree. It turns out that a Skew heap works great for this. The following Cartesian skew tree now approaches the speed of quick sort (number of compares) for random data while maintaining linear time for nearly sorted data.

I added a quick sort for comparison.




algorithms.sort.cartesian_tree_skew = function(array, predicate, profile) {
    var swapChildren = function(node) {
        var temp = node.left;
        node.left = node.right;
        node.right = temp;
    };
    
    var length = array.length;
    if (length <= 1) return;
    
    // parent could be removed with the use of a stack
    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;
        }
    }
    
    i = 0;
    while (root) {
        array[i] = root.value;
        i++;

        if (!root.left) {
            root = root.right;
            continue;
        }
        
        if (!root.right) {
            root = root.left;
            continue;
        }

        if (predicate(root.left.value, root.right.value)) {
            var insert = root.right;
            root = root.left;
        } else {
            var insert = root.left;
            root = root.right;
        }

        var next = root;
        do {
            if (!next.right) {
                next.right = insert;
                break;
            }

            if (predicate(next.right.value, insert.value)) {
                next = next.right;
            } else {
                var temp = next.right;
                next.right = insert;
                swapChildren(insert);
                insert = temp;
            }
        } while (true);
    }
};

Filed under , , , having