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: expected.