Persistent Treap

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 $O(\log n)$ new nodes. Rotations also create new nodes for affected paths.