Split by key (create new nodes for the split path):
function split(root, key)
if root is null then
return (null, null)
newRoot := copy(root)
if key < root.key then
(left, right) := split(root.left, key)
newRoot.left := right
return (left, newRoot)
else
(left, right) := split(root.right, key)
newRoot.right := left
return (newRoot, right)
Merge (also creates new nodes):
function merge(left, right)
if left is null then return right
if right is null then return left
if left.priority > right.priority then
newNode := copy(left)
newNode.right := merge(left.right, right)
return newNode
else
newNode := copy(right)
newNode.left := merge(left, right.left)
return newNode
Time: . Space: new nodes per operation.