Treap Operations - Merge

Merge combines two treaps where all keys in the first are less than all keys in the second.

function merge(left, right)
    if left is null then
        return right
    if right is null then
        return left

    if left.priority > right.priority then
        left.right := merge(left.right, right)
        return left
    else
        right.left := merge(left, right.left)
        return right

The higher-priority node becomes the root. Its appropriate subtree is recursively merged with the other treap.

Time: $O(\log n)$ expected.