Problem:

Treap

  A binary search tree can be unbalanced depending on features of data. For example, if we insert $n$ elements into a binary search tree in ascending order, the tree become a list, leading to long search times. One of strategies is to randomly shuffle the elements to be inserted. However, we should consider to maintain the balanced binary tree where different operations can be performed one by one depending on requirement.

  We can maintain the balanced binary search tree by assigning a priority randomly selected to each node and by ordering nodes based on the following properties. Here, we assume that all priorities are distinct and also that all keys are distinct.

  
binary-search-tree property. If $v$ is a left child of $u$, then $v.key right child of $u$, then $u.key heap property. If $v$ is a child of $u$, then $v.priority 

  Insert

  To insert a new element into a Treap, first of all, insert a node which a randomly selected priority value is assigned in the same way for ordinal binary search tree. For example, the following figure shows the Treap after a node with key = 6 and priority = 90 is inserted.

It is clear that this Treap violates the heap property, so we need to modify the structure of the tree by rotate operations. The rotate operation is to change parent-child relation while maintaing the binary-search-tree property.

  The rotate operations can be implemented as follows.

  

    

rightRotate(Node t)
    Node s = t.left
    t.left = s.right
    s.right = t
    return s // the new root of subtree

leftRotate(Node t)
    Node s = t.right
    t.right = s.left
    s.left = t
    return s // the new root of subtree

  The following figure shows processes of the rotate operations after the insert operation to maintain the properties.

  The insert operation with rotate operations can be implemented as follows.

insert(Node t, int key, int priority)            // search the corresponding place recursively
    if t == NIL
        return Node(key, priority)               // create a new node when you reach a leaf
    if key == t.key
        return t                                 // ignore duplicated keys

    if key Delete

  To delete a node from the Treap, first of all, the target node should be moved until it becomes a leaf by rotate operations. Then, you can remove the node (the leaf). These processes can be implemented as follows.

delete(Node t, int key)                        // seach the target recursively
    if t == NIL
        return NIL
    if key  t.key
        t.right = delete(t.right, key)
    else
        return _delete(t, key)
    return t

_delete(Node t, int key)                       // if t is the target node
    if t.left == NIL && t.right == NIL         // if t is a leaf
        return NIL
    else if t.left == NIL                      // if t has only the right child, then perform left rotate
        t = leftRotate(t)
    else if t.right == NIL                     // if t has only the left child, then perform right rotate
        t = rightRotate(t)
    else                                       // if t has both the left and right child
        if t.left.priority > t.right.priority  // pull up the child with higher priority
            t = rightRotate(t)
        else
            t = leftRotate(t)
    return delete(t, key)

  Write a program which performs the following operations to a Treap $T$ based on the above described algorithm.

insert ($k$, $p$): Insert a node containing $k$ as key and $p$ as priority to $T$.

find ($k$): Report whether $T$ has a node containing $k$.

delete ($k$): Delete a node containing $k$.

print(): Print the keys of the binary search tree by inorder tree walk and preorder tree walk respectively.

Input

    

In the first line, the number of operations $m$ is given. In the following $m$ lines, operations represented by insert $k \; p$, find $k$, delete $k$ or print are given.

Output

For each find($k$) operation, print "yes" if $T$ has a node containing $k$, "no" if not.

  In addition, for each print operation, print a list of keys obtained by inorder tree walk and preorder tree walk in a line respectively. Put a space character before each key.

Constraints

The number of operations $ \leq 200,000$

$0 \leq k, p  \leq 2,000,000,000$

The height of the binary tree does not exceed 50 if you employ the above algorithm

The keys in the binary search tree are all different.

The priorities in the binary search tree are all different.

The size of output $\leq 10$ MB

Sample Input 1

16
insert 35 99
insert 3 80
insert 1 53
insert 14 25
insert 80 76
insert 42 3
insert 86 47
insert 21 12
insert 7 10
insert 6 90
print
find 21
find 22
delete 35
delete 99
print

Sample Output 1

 1 3 6 7 14 21 35 42 80 86
 35 6 3 1 14 7 21 80 42 86
yes
no
 1 3 6 7 14 21 42 80 86
 6 3 1 80 14 7 21 42 86

Reference

  
Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.

  
Randomized Search Trees, R. Seidel, C.R. Aragon.



Sample input:
16
insert 35 99
insert 3 80
insert 1 53
insert 14 25
insert 80 76
insert 42 3
insert 86 47
insert 21 12
insert 7 10
insert 6 90
print
find 21
find 22
delete 35
delete 99
print


Sample output:
 1 3 6 7 14 21 35 42 80 86
 35 6 3 1 14 7 21 80 42 86
yes
no
 1 3 6 7 14 21 42 80 86
 6 3 1 80 14 7 21 42 86

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, key, priority):
        self.key = key
        self.priority = priority
        self.parent = None
        self.left = self.right = None
    def preorder(self):
        L = [self.key]
        if self.left: L += self.left.preorder()
        if self.right: L += self.right.preorder()
        return L
    def inorder(self):
        L = []
        if self.left: L += self.left.inorder()
        L.append(self.key)
        if self.right: L += self.right.inorder()
        return L

def rightRotate(t):
    s = t.left
    t.left = s.right
    s.right = t
    return s # root of the subtree
def leftRotate(t):
    s = t.right
    t.right = s.left
    s.left = t
    return s # root of the subtree

def insert(t, key, priority):
    if not t:
        return Node(key, priority) # 葉に到達したら新しい節点を生成して返す
    if key == t.key:
        return t # 重複したkeyは無視
    if key < t.key: # 左の子に移動
        t.left = insert(t.left, key, priority) # 左の子へのポインタを更新
        if t.priority < t.left.priority: # 左の子の方が優先度が高い場合右回転
            t = rightRotate(t)
    else: # 右の子へ移動
        t.right = insert(t.right, key, priority) # 右の子へのポインタを更新
        if t.priority < t.right.priority: # 右の子の方が優先度が高い場合左回転
            t = leftRotate(t)
    return t

def delete(t, key):
    if not t:
        return None
    if key < t.key: # 削除対象を検索
        t.left = delete(t.left, key)
    elif key > t.key:
        t.right = delete(t.right, key)
    else:
        return _delete(t, key)
    return t
def _delete(t, key):
    if not t.left and not t.right: # 葉の場合
        return None
    if not t.left: # 右の子のみを持つ場合左回転
        t = leftRotate(t)
    elif not t.right: # 左の子のみを持つ場合右回転
        t = rightRotate(t)
    else: # 左の子と右の子を両方持つ場合、優先度が高い方を持ち上げる
        if t.left.priority > t.right.priority:
            t = rightRotate(t)
        else:
            t = leftRotate(t)
    return delete(t, key)

def find(t, k):
    x = t
    while x:
        if x.key == k:
            return x
        x = x.left if k < x.key else x.right
    return None

t = None
m = int(input())
for _ in range(m):
    cmd = list(input().split())
    if cmd[0] == 'insert':
        t = insert(t, int(cmd[1]), int(cmd[2]))
    if cmd[0] == 'find':
        print('yes' if find(t, int(cmd[1])) else 'no')
    if cmd[0] == 'delete':
        t = delete(t, int(cmd[1]))
    if cmd[0] == 'print':
        print('', *t.inorder())
        print('', *t.preorder())

Submission status: Accepted

Solution code:
import sys, collections
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

class Node():
    key = None
    priority = None
    p = None
    left = None
    right = None

    def __init__(self, key, priority):
        self.key = key
        self.priority = priority

class BinarySearchTree():
    root = None

    def rightRotate(self, t):
        s = t.left
        t.left = s.right
        s.right = t
        return s

    def leftRotate(self, t):
        s = t.right
        t.right = s.left
        s.left = t
        return s

    def insert(self, t, key, priority):
        if t is None:
            return Node(key, priority)
        if key==t.key:
            return t

        if key < t.key:
            t.left = self.insert(t.left, key, priority)
            if t.priority < t.left.priority:
                t = self.rightRotate(t)
        else:
            t.right = self.insert(t.right, key, priority)
            if t.priority < t.right.priority:
                t = self.leftRotate(t)
        
        return t

    def find(self, k):
        x = self.root
        while x is not None:
            if x.key==k:
                return x
            elif x.key>k:
                x = x.left
            else:
                x = x.right
        return None

    def next_node(self, z):
        if z.right is None:
            x = z
            y = z.p
            while y is not None and y.left!=x:
                x = y
                y = y.p
            return y
        else:
            x = z.right
            while x is not None:
                y = x
                x = x.left
            return y

    def delete(self, t, key):
        if t is None:
            return None
        if key < t.key:
            t.left = self.delete(t.left, key)
        elif key > t.key:
            t.right = self.delete(t.right, key)
        else:
            return self._delete(t, key)
        return t

    def _delete(self, t, key):
        if t.left is None and t.right is None:
            return None
        elif t.left is None:
            t = self.leftRotate(t)
        elif t.right is None:
            t = self.rightRotate(t)
        else:
            if t.left.priority > t.right.priority:
                t = self.rightRotate(t)
            else:
                t = self.leftRotate(t)
        return self.delete(t, key)
            
    def print_nodes(self):
        inorder = []
        preorder = []

        def dfs(v):
            v_key = v.key
            preorder.append(v_key)
            if v.left is not None:
                dfs(v.left)
            inorder.append(v_key)
            if v.right is not None:
                dfs(v.right)

        dfs(self.root)

        print('', *inorder)
        print('', *preorder)

def resolve():
    m = I()
    T = BinarySearchTree()
    for _ in range(m):
        q = LSS()
        if q[0]=='insert':
            k = int(q[1])
            p = int(q[2])
            T.root = T.insert(T.root, k, p)
        elif q[0]=='find':
            k = int(q[1])
            if T.find(k):
                print('yes')
            else:
                print('no')
        elif q[0]=='delete':
            k = int(q[1])
            T.root = T.delete(T.root, k)
        else:
            T.print_nodes()

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
class Node:
    def __init__(self,key,priority,left=None,right=None):
        self.left = left
        self.right = right
        self.key = key
        self.priority = priority

def insert(t,key,priority):
    if t == None :
        return Node(key,priority)
    if key == t.key :
        return t
    if key < t.key :
        t.left = insert(t.left, key, priority)
        if t.priority < t.left.priority :
            t = rightRotate(t)
    else:
        t.right = insert(t.right, key, priority)
        if t.priority < t.right.priority :
            t = leftRotate(t)
    return t


def rightRotate(t):
    s = t.left
    t.left = s.right
    s.right = t
    return s


def leftRotate(t):
    s= t.right
    t.right = s.left
    s.left = t
    return s


def find(t,key):
    if t == None: return None
    elif t.key == key:return t
    elif t.key > key :return find(t.left,key)
    else: return find(t.right,key)

def erase(t, key):
    if t == None : return None
    if key == t.key:
        if t.left == None and t.right == None:return None
        elif t.left == None : t = leftRotate(t)
        elif t.right == None : t = rightRotate(t)
        else:
            if t.left.priority > t.right.priority:t = rightRotate(t)
            else: t = leftRotate(t)
        return erase(t, key)
    elif key < t.key : t.left = erase(t.left, key)
    else : t.right = erase(t.right, key)
    return t

def inorder(t):
    if t.left != None:inorder(t.left)
    print(" "+str(t.key), end='')
    if t.right != None: inorder(t.right)

def preorder(t):
    print(" "+str(t.key), end='')
    if t.left != None :preorder(t.left)
    if t.right != None : preorder(t.right)

if __name__=="__main__":
        m=(int)(input())
        root = None
        for i in range(m):
            order = input().split()
            if order[0] == "insert" :root = insert(root,(int)(order[1]),(int)(order[2]))
            elif order[0] == "delete" :root = erase(root,(int)(order[1]))
            elif order[0] == "find" :
                res = find(root,(int)(order[1]))
                if res == None :print("no")
                else:print("yes")
            else:
                inorder(root)
                print()
                preorder(root)
                print()

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, x, priority):
        self.data = x
        self.priority = priority
        self.left = None
        self.right = None

def rightRotate(node):
    leftNode = node.left
    node.left = leftNode.right
    leftNode.right = node
    return leftNode

def leftRotate(node):
    rightNode = node.right
    node.right = rightNode.left
    rightNode.left = node
    return rightNode

def find(node, x):
    while node is not None:
        if x == node.data:
            return True
        elif x < node.data:
            node = node.left
        else:
            node = node.right
    return False

def insert(node, x, priority):
    if node is None:
        return Node(x, priority)

    if x == node.data:
        return node

    if x < node.data:
        node.left = insert(node.left, x, priority)
        if node.priority < node.left.priority:
            node = rightRotate(node)

    else:
        node.right = insert(node.right, x, priority)
        if node.priority < node.right.priority:
            node = leftRotate(node)
    return node

def inorder_print(node, x = 0):
    if node is not None:
        print('',node.data, end = '')
        inorder_print(node.left, x + 1)
        inorder_print(node.right, x + 1)

def preorder_print(node, x = 0):
    if node is not None:
        preorder_print(node.left, x + 1)
        print('',node.data, end = '')
        preorder_print(node.right, x + 1)


def delete(node, x):
    if node == None:
        return None
    if x < node.data:
        node.left = delete(node.left, x)
    elif x > node.data:
        node.right = delete(node.right, x)
    else:
        return _delete(node, x)

    return node

def _delete(node, x):
    if node.left == None and node.right == None:
        return None
    elif node.left == None:
        node = leftRotate(node)
    elif node.right == None:
        node = rightRotate(node)
    else:
        if node.left.priority > node.right.priority:
            node = rightRotate(node)
        else:
            node = leftRotate(node)
    return delete(node, x)

class Treap:
    def __init__(self):
        self.root = None

    def find_(self, x):
        return find(self.root, x)

    def insert_(self, x, pri):
        self.root = insert(self.root, x, pri)

    def delete_(self, x):
        self.root = delete(self.root, x)

    def traverse_(self):
        for x in traverse(self.root):
            yield x

    def print_treap_(self):
        preorder_print(self.root)
        print('')
        inorder_print(self.root)
        print('')

if __name__ == '__main__':

    n = int(input())
    treap = Treap()
    for i in range(n):
        _input = input()
        if _input == 'print':
            #print operation
            treap.print_treap_()

        else:
            operate, nums = _input.split(' ', 1)
            if operate == 'insert':
                #insert operation
                k, p = (int(z) for z in nums.split())
                treap.insert_(k, p)

            elif operate == 'find':
                k = int(nums)
                res = treap.find_(k)
                if res:
                    print("yes")
                else:
                    print("no")

            elif operate == 'delete':
                k = int(nums)
                treap.delete_(k)

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, key, priority, left=None, right=None):
        self.key = key
        self.priority = priority
        self.left = left
        self.right = right


def rightRotate(t):
    s = t.left
    t.left = s.right
    s.right = t
    return s # 部分木の新しい根を返す


def leftRotate(t):
    s = t.right
    t.right = s.left
    s.left = t
    return s # 部分木の新しい根を返す


def insert(t, key, priority):
    # 葉に到達したらノードを生成して返す
    if t == None:
        return Node(key, priority)
    # 重複するキーを無視する
    if key == t.key:
        return t

    if key < t.key: # 左の子に移動
        # 帰ってきたノードを左の子にする
        t.left = insert(t.left, key, priority)
        # その子に優先度が高ければ、右回転で持ち上げる
        if t.priority < t.left.priority:
            t = rightRotate(t)
    else: # 右の子に移動
        # 帰ってきたノードを右の子にする
        t.right = insert(t.right, key, priority)
        # その子の優先度が高ければ左回転で持ち上げる
        if t.priority < t.right.priority:
            t = leftRotate(t)

    return t


def erase(t, key):
    if t == None:
        return None

    if key == t.key: # tが削除対象
        if (t.left == None) and (t.right == None): # tが葉
            return None
        elif t.left == None: # tがただ一つの右の子を持つ
            t = leftRotate(t)
        elif t.right == None:
            t = rightRotate(t) # tがただ一つの左の子を持つ
        else: # tが二つの子を持つ
            # 優先度が高い子を持ち上げる
            if t.left.priority > t.right.priority:
                t = rightRotate(t)
            else:
                t = leftRotate(t)
        return erase(t, key)

    # 対象を再帰的に探索
    elif key > t.key:
        t.right = erase(t.right, key)
    else:
        t.left = erase(t.left, key)
    return t


# 引数のkeyを持つノードの有無を探索
def find(t, key):
    if t.key == key:
        print("yes")
    elif t.key < key and t.right != None:
        find(t.right, key)
    elif t.key > key and t.left != None:
        find(t.left, key)
    else:
        print("no")
    return 0


def in_print(t):
    if t.left != None:
        in_print(t.left)
    print(" " + str(t.key), end='')
    if t.right != None:
        in_print(t.right)

# 中間巡回アルゴリズム
def pre_print(t):
    print(" " + str(t.key), end='')
    if t.left != None:
        pre_print(t.left)
    if t.right != None:
        pre_print(t.right)


def main():
    Treap = None
    p = []
    k = int(input())
    i = 0
    while i < k:
        try:
            p.append(list(map(str, input().split())))
            i = i + 1
        except:
            break;
    
    i = 0
    while i < k:
        if p[i][0] == 'insert':
            key = int(p[i][1])
            priority = int(p[i][2])
            Treap = insert(Treap, key, priority)
        elif p[i][0] == 'find':
            key = int(p[i][1])
            find(Treap, key)
        elif p[i][0] == 'delete':
            key = int(p[i][1])
            Treap = erase(Treap, key)
        else:
            in_print(Treap)
            print()
            pre_print(Treap)
            print()
        i = i + 1

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def rotate(nd, d):
    c = nd[d]
    if d:
        nd[1] = c[0]
        c[0] = nd
    else:
        nd[0] = c[1]
        c[1] = nd
    return c


root = None
def insert(val, pri):
    global root
    st = []
    dr = []
    x = root
    while x:
        st.append(x)
        if x[2] == val:
            return
        d = (x[2] < val)
        dr.append(d)
        x = x[d]
    nd = [None, None, val, pri]
    while st:
        x = st.pop(); d = dr.pop()
        c = x[d] = nd
        if x[3] >= c[3]:
            break
        rotate(x, d)
    else:
        root = nd

def __delete(nd):
    st = []; dr = []
    while nd[0] or nd[1]:
        l = nd[0]; r = nd[1]
        d = (l[3] <= r[3]) if l and r else (l is None)
        st.append(rotate(nd, d))
        dr.append(d ^ 1)
    nd = x = None
    while st:
        nd = x; x = st.pop(); d = dr.pop()
        x[d] = nd
    return x

def delete(val):
    global root
    x = root

    y = None
    while x:
        if val == x[2]:
            break
        y = x; d = (x[2] < val)
        x = x[d]
    else:
        return

    if y:
        y[d] = __delete(x)
    else:
        root = __delete(x)

def find(val):
    x = root
    while x:
        if val == x[2]:
            return 1
        x = x[x[2] < val]
    return 0

def debug():
    s0 = [""]
    s1 = [""]

    def dfs(nd):
        v = str(nd[2])
        s0.append(v)
        if nd[0]:
            dfs(nd[0])
        s1.append(v)
        if nd[1]:
            dfs(nd[1])
    dfs(root)
    return " ".join(s1), " ".join(s0)


M = int(readline())
ans = []
for m in range(M):
    cmd, *V, = readline().split()
    if cmd == "print":
        ans.extend(debug())
    elif cmd == "find":
        ans.append("yes" if find(int(V[0])) else "no")
    elif cmd == "delete":
        delete(int(V[0]))
    else:
        val, pri = map(int, V)
        insert(val, pri)
write("\n".join(ans))
write("\n")

Submission status: Accepted

Solution code:
def lrotate(t):
    s = t.right
    t.right = s.left
    s.left = t
    return s

def rrotate(t):
    s = t.left
    t.left = s.right
    s.right = t
    return s

def insert(t, key, pri):
    if t == None:
        return Treap(key, pri)
    if key == t.key:
        return t

    if key < t.key:
        t.left = insert(t.left, key, pri)
        if t.pri < t.left.pri:
            t = rrotate(t)
    else:
        t.right = insert(t.right, key, pri)
        if t.pri < t.right.pri:
            t = lrotate(t)
    return t

def delete(t, key):
    if t == None:
        return None

    if key == t.key:
        if t.left == None and t.right == None:
            return None
        elif t.left == None:
            t = lrotate(t)
        elif t.right == None:
            t = rrotate(t)
        else:
            if t.left.pri > t.right.pri:
                t = rrotate(t)
            else:
                t = lrotate(t)
        return delete(t, key)

    if key < t.key:
        t.left = delete(t.left, key)
    else:
        t.right = delete(t.right, key)
    return t

def find(t, key):
    if t == None:
        return -1
    if t.key == key:
        return 1
    if key < t.key:
        return find(t.left, key)
    else:
        return find(t.right, key)
    
def inorder(t):
    if t == None:
        return 
    inorder(t.left)
    print(" " + str(t.key), end="")
    inorder(t.right)

def preorder(t):
    if t == None:
        return
    print(" " + str(t.key), end="")
    preorder(t.left)
    preorder(t.right)



class Treap():
    def __init__(self, key, pri):
        self.key = key
        self.pri = pri
        self.left = None
        self.right = None
        
t = None
data = []
m = int(input())
for i in range(m):
    data.append(list(input().split()))

for i in range(m):
    if data[i][0] == "insert":
        t = insert(t, int(data[i][1]), int(data[i][2]))
    elif data[i][0] == "delete":
        t = delete(t, int(data[i][1]))
    elif data[i][0] == "find":
        result = find(t, int(data[i][1]))
        if result == 1:
            print("yes")
        else:
            print("no")
    else:
        inorder(t)
        print()
        preorder(t)
        print()

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, key:int, priority:int):
        self.key = key
        self.priority = priority
        self.left = None
        self.right = None

class Tree:
    def __init__(self):
        self.root = None

    def leftRotate(self, t:Node):
        s:Node = t.right
        t.right = s.left
        s.left = t
        if t.key == self.root.key:
            self.root = s
        return s

    def rightRotate(self, t:Node):
        s:Node = t.left
        t.left = s.right
        s.right = t
        if t.key == self.root.key:
            self.root = s        
        return s

    def insert(self, t:Node, key:int, priority:int):
        if not self.root:
            self.root = Node(key, priority)
            return self.root
        if not t:
            return Node(key, priority)
        if key == t.key:
            return t
        if key < t.key:
            t.left = self.insert(t.left, key, priority)
            if t.priority < t.left.priority:
                t = self.rightRotate(t)
        else:
            t.right = self.insert(t.right, key, priority)
            if t.priority < t.right.priority:
                t = self.leftRotate(t)
        return t

    def delete(self, t:Node, key:int):
        if not t:
            return None
        if key < t.key:
            t.left = self.delete(t.left, key)
        elif key > t.key:
            t.right = self.delete(t.right, key)
        else:
            return self._delete(t, key)
        return t

    def _delete(self, t:Node, key:int):
        if not t.left and not t.right:
            return None
        elif not t.left:
            t = self.leftRotate(t)
        elif not t.right:
            t = self.rightRotate(t)
        else:
            if t.left.priority > t.right.priority:
                t = self.rightRotate(t)
            else:
                t = self.leftRotate(t)
        return self.delete(t, key)


def Preorder(target:Node):
    yield target.key
    if target.left != None:
        yield from Preorder(target.left)
    if target.right != None:
        yield from Preorder(target.right)

def Inorder(target:Node):
    if target.left != None:
        yield from Inorder(target.left)
    yield target.key
    if target.right != None:
        yield from Inorder(target.right)

def find(target:Node,findkey:int):
    return node_of_key(target, findkey) != None

def node_of_key(target:Node,findkey:int):
    if target.key == findkey:
        return target
    elif target.key > findkey:
        if target.left:
            return node_of_key(target.left, findkey)
    else:
        if target.right:
            return node_of_key(target.right, findkey)
    return None

def min_value_node_of_tree(root:Node):
    if root.left == None:
        return root
    else:
        return min_value_node_of_tree(root.left)


from sys import stdin
tree = Tree()
n = int(input())
lines = stdin.readlines()
for line in lines:
    proc,*param = line.split()
    if proc == "insert":
        if not tree.root:
            tree.root = Node(int(param[0]), int(param[1]))
        else:
            tree.insert(tree.root, int(param[0]), int(param[1]))
    elif proc == "find":
        print("yes" if find(tree.root, int(param[0])) else "no")
    elif proc == "delete":
        tree.delete(tree.root, int(param[0]))
    else:
        print(" ",end="")
        print(*Inorder(tree.root))
        print(" ",end="")
        print(*Preorder(tree.root))

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, k, p):
        self.k, self.p = k, p
        self.left, self.right = None, None

class Treap:
    def __init__(self):
        self.root = None
    
    def insert(self, k, p):
        self.root = self.__insert(self.root, k, p)

    def rightRotate(self, t):
        s = t.left
        t.left = s.right
        s.right = t
        return s
    
    def leftRotate(self, t):
        s = t.right
        t.right = s.left
        s.left = t
        return s

    def __insert(self, t, k , p):
        if t == None:
            return Node(k, p)
        if k == t.k:
            return t
        
        if k < t.k:
            t.left = self.__insert(t.left, k, p)
            if t.p < t.left.p:
                t = self.rightRotate(t)
        else:
            t.right = self.__insert(t.right, k, p)
            if t.p < t.right.p:
                t = self.leftRotate(t)
        return t
    
    def delete(self, k):
        self.root = self._delete(k)
        
    def _delete(self, k, t = -1):
        if t == -1:
            t = self.root
        
        if t == None:
            return None
        if k < t.k:
            t.left = self._delete(k, t.left)
        elif k > t.k:
            t.right = self._delete(k, t.right)
        else:
            return self.__delete(t, k)
        return t
    
    def __delete(self, t, k):
        if t.left == None and t.right == None:
            return None
        elif t.left == None:
            t = self.leftRotate(t)
        elif t.right == None:
            t = self.rightRotate(t)
        else:
            if t.left.p > t.right.p:
                t = self.rightRotate(t)
            else:
                t = self.leftRotate(t)
        return self._delete(k, t)

    def find(self, k, t = -1):
        if t == -1:
            t = self.root
        if t == None:
            return None
        if k < t.k:
            return self.find(k, t.left)
        elif k > t.k:
            return self.find(k, t.right)
        else:
            return t
    
    def preOrder(self, r = -1):
        if r == -1: r = self.root
        if r == None:   return
        print("", r.k, end = '')
        self.preOrder(r.left)
        self.preOrder(r.right)
    
    def inOrder(self, r = -1):
        if r == -1: r = self.root
        if r == None:   return
        self.inOrder(r.left)
        print("", r.k, end = '')
        self.inOrder(r.right)
    
    def print(self):
        self.inOrder()
        print()
        self.preOrder()
        print()

tree = Treap()
for _ in range(int(input())):
    In = input().split()
    if In[0][0] == 'i':
        tree.insert(int(In[1]), int(In[2]))
    elif In[0][0] == 'p':
        tree.print()
    elif In[0][0] == 'f':
        print(['no', 'yes'][tree.find(int(In[1])) != None])
    elif In[0][0] == 'd':
        tree.delete(int(In[1]))