Treaps (tree + heap) combine BST and heap properties:
- BST property on keys
- Heap property on random priorities
Persistence via path copying:
function insert(root, key, priority)
if root is null then
return new Node(key, priority)
newRoot := copy(root)
if key < root.key then
newRoot.left := insert(root.left, key, priority)
if newRoot.left.priority > newRoot.priority then
newRoot := rotateRight(newRoot)
else
newRoot.right := insert(root.right, key, priority)
if newRoot.right.priority > newRoot.priority then
newRoot := rotateLeft(newRoot)
return newRoot
Each insert creates new nodes. Rotations also create new nodes for affected paths.