Cartesian Tree Sort - Revisited

Friday, June 25, 2010 by gradbot

Thinking about Cartesian tree sort some more it seems logical to also use the Cartesian tree as the priority queue since it is already a heap. Performance appears to be the same without the extra memory requirement of an external priority queue.



algorithms.sort.cartesian_tree_erik = function(array, predicate) {
    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;
        }
    }
            
    var 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.left;
            root = root.right;
        } else {
            var insert = root.right;
            root = root.left;
        }
                
        var next = root;
        do {
            if (!next.left) {
                next.left = insert;
                break;
            }
                    
            if (!next.right) {
                next.right = insert;
                break;
            }

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

Filed under , , , having  

0 comments: