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:
# Treap
class Node():
    def __init__(self, k, p):
        self.k = k
        self.p = p
        self.left = None
        self.right = None

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, pri):
    if t == None:
        return Node(key, pri)
    if key == t.k:
        return t

    if key < t.k:
        t.left = insert(t.left, key, pri)
        if t.p < t.left.p:
            t = rightRotate(t)
    else:
        t.right = insert(t.right, key, pri)
        if t.p < t.right.p:
            t = leftRotate(t)
    return t

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

    if key == t.k:
        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.p > t.right.p:
                t = rightRotate(t)
            else:
                t = leftRotate(t)
        return erase(t, key)

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

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

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

def output(t):
    inorder(t)
    print()
    preorder(t)
    print()


t = None
data = []
dict = {}
m = int(input())
for i in range(m):
    data.append(list(input().split()))

for i in range(m):
    if data[i][0] == "insert":
        if (data[i][1] in dict) == False:
            t = insert(t, int(data[i][1]), int(data[i][2]))
            dict[data[i][1]] = True
    elif data[i][0] == "print":
        output(t)
    elif data[i][0] == "find":
        if (data[i][1] in dict) == True:
            print("yes")
        else:
            print("no")
    else:
        t = erase(t, int(data[i][1]))
        if (data[i][1] in dict) == True:
            del dict[data[i][1]]

Submission status: Accepted

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

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, pri):
    if t == None:
        return Node(key, pri)
    if key == t.k:
        return t

    if key < t.k:
        t.left = insert(t.left, key, pri)
        if t.p < t.left.p:
            t = rightRotate(t)
    else:
        t.right = insert(t.right, key, pri)
        if t.p < t.right.p:
            t = leftRotate(t)
    return t

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

    if key == t.k:
        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.p > t.right.p:
                t = rightRotate(t)
            else:
                t = leftRotate(t)
        return erase(t, key)

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

def find(t, k):
    if t == None:
        return -1
    if t.k == k:
        return 1
    if k < t.k:
        return find(t.left, k)
    else:
        return find(t.right, k)

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

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

def output(t):
    inorder(t)
    print()
    preorder(t)
    print()


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] == "print":
        output(t)
    elif data[i][0] == "find":
        result = find(t, int(data[i][1]))
        if result == 1:
            print("yes")
        else:
            print("no")
    else:
        t = erase(t, int(data[i][1]))

Submission status: Accepted

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

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

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

def insert(t, key, pri):
    if t == None:
        return Node(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 find(x, k):
    while x != None and k != x.key:
        if x.key != None:
            if k < x.key:
                x = x.left
            else:
                x = x.right
    return x

def delete(t, key):
    if t == None:
        return None
    if key < t.key:
        t.left = delete(t.left, key)
    elif key > t.key:
        t.right = delete(t.right, key)
    else:
        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)
    return t

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

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

count = int(input())
t = None
for i in range(count):
    a = input().split()
    if a[0] == 'insert':
        t = insert(t, int(a[1]), int(a[2]))
    elif a[0] == 'find':
        if find(t, int(a[1])) == None:
            print('no')
        else:
            print('yes')
    elif a[0] == 'delete':
        t = delete(t, int(a[1]))
    else:
        inorder(t)
        print('\n', end="")
        preorder(t)
        print('\n', end="")

Submission status: Accepted

Solution code:
# coding:utf-8

NIL =  None

class Node():
	def __init__(self, key, pri):
		self.key = key
		self.pri = pri
		self.right = NIL
		self.left = NIL


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, pri):
	if t == NIL:
		return Node(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 = rightRotate(t)
	else :
		t.right = insert(t.right, key, pri)
		if t.pri < t.right.pri:
			t = leftRotate(t)

	return t

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

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

	return t

def find(t, key):
	if t == NIL:
		return False
	if key == t.key:
		return True

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


head = Node(-1, 2000000001)

def print_priorder(t):
	if t == NIL:
		return

	if t != head:
		print(" " + str(t.key), end='')

	print_priorder(t.left)
	print_priorder(t.right)

def print_inorder(t):
	if t == NIL:
		return

	print_inorder(t.left)
	if t != head:
		print(" " + str(t.key), end='')
	print_inorder(t.right)


n = int(input()) # 命令の数

for i in range(n):
	inst = input().split()

	if inst[0] == "insert":
		insert(head, int(inst[1]), int(inst[2]))

	elif inst[0] == "find":
		if find(head, int(inst[1])):
			print("yes")
		else :
			print("no")

	elif inst[0] == "delete":
		erase(head, int(inst[1]))

	elif inst[0] == "print":
		print_inorder(head)
		print()
		print_priorder(head)
		print()

Submission status: Accepted

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


def rRotate(t):
    s       = t.left
    t.left  = s.right
    s.right = t

    return s


def lRotate(t):
    s       = t.right
    t.right = s.left
    s.left  = t

    return s


def insert(t, key, pri):
    if t == None: return Node(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:
        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 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)


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

def preorder(t):
    if(t == None): return

    print('', t.key, end='')
    preorder(t.left )
    preorder(t.right)


def inorder(t):
    if(t == None): return

    inorder(t.left )
    print('', t.key, end='')
    inorder(t.right)


if __name__ == '__main__':
    n = int(input())
    top = None

    for _ in range(n):
        strs = input().split()

        op  = strs[0]
        if op != 'print':
            key = int(strs[1])
            if op == 'insert':
                pri = int(strs[2])

        if op == 'insert': top = insert(top, key, pri)
        if op == 'delete': top = delete(top, key)
        if op == 'find'  :
            if find(top, key): print('yes')
            else           : print('no' )
        if op == 'print' :
            inorder(top)
            print()
            preorder(top)
            print()

Submission status: Accepted

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


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, pri):
    if t == None:
        return Node(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 = rightRotate(t)
    else:
        t.right = insert(t.right, key, pri)
        if t.pri < t.right.pri:
            t = leftRotate(t)

    return t


def delete(t, key):
    if   t == None:
        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 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.pri > t.right.pri:
            t = rightRotate(t)
        else:
            t = leftRotate(t)
    return delete(t, key)


def find(t, key):
    if t == None:
        return False

    if key == t.key:
        return True

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

def priorder(t):
    if t == None:
        return

    print(' ' + str(t.key), end='')
    priorder(t.left)
    priorder(t.right)

def inorder(t):
    if t == None:
        return

    inorder(t.left)
    print(' ' + str(t.key), end='')
    inorder(t.right)


m = int(input())
t = None

for _ in range(m):
    com = input().split()

    if com[0] == 'insert':
        t = insert(t, int(com[1]), int(com[2]))
    elif com[0] == 'find':
        if find(t, int(com[1])):
            print('yes')
        else :
            print('no')
    elif com[0] == 'delete':
        t = delete(t, int(com[1]))
    elif com[0] == 'print':
        inorder(t)
        print()
        priorder(t)
        print()

Submission status: Accepted

Solution code:
import sys
from collections import namedtuple


Node = namedtuple('Node', ['key', 'priority', 'left', 'right'])


class Treap:
    MAX_KEY = 2000000000
    MAX_PRIORITY = 2000000000

    def __init__(self):
        self.root = None

    def insert(self, key, priority):
        def _insert(node):
            if node is None:
                return Node(key, priority, None, None)
            k, p, left, right = node
            if key < k:
                node = Node(k, p, _insert(left), right)
                if p < node.left.priority:
                    node = self._rotate_right(node)
            elif key > k:
                node = Node(k, p, left, _insert(right))
                if p < node.right.priority:
                    node = self._rotate_left(node)
            else:  # node.key == key
                pass
            # assert(self._bst_invariant(node))
            # assert(self._heap_invariant(node))
            return node

        self.root = _insert(self.root)

    def delete(self, key):
        def _delete(node):
            if node is None:
                return None
            k, p, left, right = node
            if key < k:
                node = node._replace(left=_delete(left))
            elif key > k:
                node = node._replace(right=_delete(right))
            else:  # key == k
                if left is None:
                    node = right
                elif right is None:
                    node = left
                else:
                    if left.priority > right.priority:
                        node = _delete(self._rotate_right(node))
                    else:
                        node = _delete(self._rotate_left(node))
            # assert(self._bst_invariant(node))
            # assert(self._heap_invariant(node))
            return node

        self.root = _delete(self.root)

    def find(self, key):
        def _find(node):
            if node is None:
                return False
            if key < node.key:
                return _find(node.left)
            elif key > node.key:
                return _find(node.right)
            else:
                return True

        return _find(self.root)

    def inorder(self):
        def _inorder(node):
            if node is not None:
                yield from _inorder(node.left)
                yield node
                yield from _inorder(node.right)
        return _inorder(self.root)

    def preorder(self):
        def _preorder(node):
            if node is not None:
                yield node
                yield from _preorder(node.left)
                yield from _preorder(node.right)
        return _preorder(self.root)

    def postorder(self):
        def _postorder(node):
            if node is not None:
                yield from _postorder(node.left)
                yield from _postorder(node.right)
                yield node
        return _postorder(self.root)

    def _rotate_left(self, node):
        # assert node.right is not None
        top = node.right
        node = node._replace(right=top.left)
        top = top._replace(left=node)
        return top

    def _rotate_right(self, node):
        # assert node.left is not None
        top = node.left
        node = node._replace(left=top.right)
        top = top._replace(right=node)
        return top

    def _heap_invariant(self, node):
        if node is None:
            return True
        key, priority, left, right = node
        return ((left is None or priority > left.priority)
                and (right is None or priority > right.priority))

    def _bst_invariant(self, node):
        if node is None:
            return True
        key, priority, left, right = node
        return ((left is None or key > left.key)
                and (right is None or key < right.key))

    def __str__(self):
        def _str(node):
            if node is None:
                return ''
            else:
                k, p, l, r = node
                return '({}[{}/{}]{})'.format(_str(l), k, p, _str(r))
        return _str(self.root)


def run():
    input()
    tree = Treap()

    for line in sys.stdin:
        if line.startswith('insert'):
            key, priority = [int(i) for i in line[7:].split()]
            tree.insert(key, priority)
        elif line.startswith('find'):
            if tree.find(int(line[5:])):
                print("yes")
            else:
                print("no")
        elif line.startswith('delete'):
            tree.delete(int(line[7:]))
        elif line.startswith('print'):
            print('', ' '.join([str(n.key) for n in tree.inorder()]))
            print('', ' '.join([str(n.key) for n in tree.preorder()]))
        else:
            raise ValueError('invalid command')
        # print(tree)


if __name__ == '__main__':
    run()

Submission status: Accepted

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

def insert(n,key,pri):
    if(n == None):
        return node(key,pri)
    if(key == n.key):
        return n
    if(key < n.key):
        n.left = insert(n.left, key, pri)
        if(n.pri < n.left.pri):
            n = rightRotate(n)
    else:
        n.right = insert(n.right, key, pri)
        if(n.pri < n.right.pri):
            n = leftRotate(n)
    return n


def rightRotate(n):
    child = n.left
    swapL,swapR,swapK,swapP = child.left,child.right,child.key,child.pri
    n.left = swapR
    n = node(swapK,swapP,swapL,n)
    return n

def leftRotate(n):
    child = n.right
    swapL,swapR,swapK,swapP = child.left,child.right,child.key,child.pri
    n.right = swapL
    n = node(swapK,swapP,n,swapR)
    return n

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

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

def _delete(n, key):
    if(n.left == None and n.right == None):
        return None
    elif(n.left == None):
        n = leftRotate(n)
    elif(n.right == None):
        n = rightRotate(n)
    else:
        if(n.left.pri > n.right.pri):
            n = rightRotate(n)
        else:
            n = leftRotate(n)
    return delete(n, key)

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

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

op_num=(int)(input())
root = None
for i in range(op_num):
    items = input().split()
    if(items[0] == "insert"):
        root = insert(root,(int)(items[1]),(int)(items[2]))
    elif(items[0] == "delete"):
        root = delete(root,(int)(items[1]))
    elif(items[0] == "find"):
        res = find(root,(int)(items[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,key,pri,left=None,right=None):
        self.left = left
        self.right = right
        self.key = key
        self.pri = pri

def insert(n,key,pri):
    if(n == None):
        return node(key,pri)
    if(key == n.key):
        return n
    if(key < n.key):
        n.left = insert(n.left, key, pri)
        if(n.pri < n.left.pri):
            n = rightRotate(n)
    else:
        n.right = insert(n.right, key, pri)
        if(n.pri < n.right.pri):
            n = leftRotate(n)
    return n

def rightRotate(n):
    child = n.left
    swapL,swapR,swapK,swapP = child.left,child.right,child.key,child.pri
    n.left = swapR
    n = node(swapK,swapP,swapL,n)
    return n

def leftRotate(n):
    child = n.right
    swapL,swapR,swapK,swapP = child.left,child.right,child.key,child.pri
    n.right = swapL
    n = node(swapK,swapP,n,swapR)
    return n

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

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

def _delete(n, key):
    if(n.left == None and n.right == None):
        return None
    elif(n.left == None):
        n = leftRotate(n)
    elif(n.right == None):
        n = rightRotate(n)
    else:
        if(n.left.pri > n.right.pri):
            n = rightRotate(n)
        else:
            n = leftRotate(n)
    return delete(n, key)

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

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

op_num=(int)(input())
root = None
for i in range(op_num):
    items = input().split()
    if(items[0] == "insert"):
        root = insert(root,(int)(items[1]),(int)(items[2]))
    elif(items[0] == "delete"):
        root = delete(root,(int)(items[1]))
    elif(items[0] == "find"):
        res = find(root,(int)(items[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, key, priority):
        self.right = None
        self.left = None
        self.parent = None
        self.key = key
        self.priority = priority

    def preorder(self):
        ret = [self.key]
        if self.left:
            ret += self.left.preorder()
        if self.right:
            ret += self.right.preorder()
        return ret

    def inorder(self):
        ret = []
        if self.left:
            ret += self.left.inorder()
        ret += [self.key]
        if self.right:
            ret += self.right.inorder()
        return ret

    def find(self, k):
        if self.key == k:
            return self
        elif self.key < k:
            if self.right:
                return self.right.find(k)
            else:
                return None
        else:
            if self.left:
                return self.left.find(k)
            else:
                return None


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

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

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

    def insert(self, k, p):
        self.root = self._insert(self.root, k, p)

    def _insert(self, t, k, p):
        if t is None:
            return Node(k, p)
        if k == t.key:
            return t
        if k < t.key:
            t.left = self._insert(t.left, k, p)
            if t.priority < t.left.priority:
                t = self.right_rotate(t)
        else:
            t.right = self._insert(t.right, k, p)
            if t.priority < t.right.priority:
                t = self.left_rotate(t)
        return t

    def print(self):
        if self.root is None:
            print()
        else:
            print('', ' '.join(map(str, self.root.inorder())))
            print('', ' '.join(map(str, self.root.preorder())))

    def find(self, k):
        if self.root is None:
            return None
        else:
            return self.root.find(k)

    def delete(self, k):
        self.root = self._delete(self.root, k)

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

    def _else_delete(self, t, k):
        if t.left is None and t.right is None:
            return None
        elif t.left is None:
            t = self.left_rotate(t)
        elif t.right is None:
            t = self.right_rotate(t)
        else:
            if t.left.priority > t.right.priority:
                t = self.right_rotate(t)
            else:
                t = self.left_rotate(t)
        return self._delete(t, k)


m = int(input())
treap = Treap()
for _ in range(m):
    s = input().split()
    if s[0] == "insert":
        treap.insert(int(s[1]), int(s[2]))
    elif s[0] == "find":
        if treap.find(int(s[1])):
            print("yes")
        else:
            print("no")
    elif s[0] == "delete":
        treap.delete(int(s[1]))
    else:
        treap.print()