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:
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:
class Node:
    def __init__(self, key, priority):
        self.key = key
        self.pri = priority
        self.parent = None
        self.left = None
        self.right = None
        
    def insert(self, z):
        if z.key < self.key:
            if self.left:
                self.left.insert(z)
            else:
                self.left = z
                z.parent = self
            if self.pri < self.left.pri:
                self.rightR()
        elif self.key < z.key:
            if self.right:
                self.right.insert(z)
            else:
                self.right = z
                z.parent = self
            if self.pri < self.right.pri:
                self.leftR()
    
    def find(self, key):
        if self.key == key:
            return True
        elif not self.left and not self.right:
            return False
        else:
            if key < self.key:
                return self.left.find(key)
            else:
                return self.right.find(key)
            
    def delete(self, key):
        if key < self.key:
            self.left.delete(key)
        elif key > self.key:
            self.right.delete(key)
        else:
            self._delete()
    
    def _delete(self):
        if not self.left and not self.right:
            if self.parent.left == self:
                self.parent.left = None
            else:
                self.parent.right = None
            del self
            return None
        elif self.left and self.right:
            if self.left.pri > self.right.pri:
                self.rightR()
            else:
                self.leftR()
        elif self.right:
            self.leftR()
        else:
            self.rightR()
        self._delete()
        
    def rightR(self):
        tmp = self.left
        if self.parent:
            if self.key < self.parent.key:
                self.parent.left = tmp
            else:
                self.parent.right = tmp
        self.left = tmp.right
        if self.left:
            self.left.parent = self
        tmp.right = self
        tmp.parent = self.parent
        self.parent = tmp
        
    def leftR(self):
        tmp = self.right
        if self.parent:
            if self.key < self.parent.key:
                self.parent.left = tmp
            else:
                self.parent.right = tmp
        self.right = tmp.left
        if self.right:
            self.right.parent = self
        tmp.left = self
        tmp.parent = self.parent
        self.parent = tmp
    
    def preo(self):
        tmp = ""
        tmp += " " + str(self.key)
        if self.left:
            tmp += self.left.preo()
        if self.right:
            tmp += self.right.preo()
        return tmp
    
    def ino(self):
        tmp = ""
        if self.left:
            tmp += self.left.ino()
        tmp += " " + str(self.key)
        if self.right:
            tmp += self.right.ino()
        return tmp

m = int(input())
root = None
for i in range(m):
    com = input().split()
    if com[0] == "insert":
        node = Node(int(com[1]), int(com[2]))
        try:
            root.insert(node)
        except AttributeError :
            root = node
    elif com[0] == "find":
        try:
            if root.find(int(com[1])):
                print("yes")
            else:
                print("no")
        except AttributeError:
            print("no")
    elif com[0] == "delete":
        try:
            root.delete(int(com[1]))
        except AttributeError:
            pass
    else:
        try:
            print(root.ino())
            print(root.preo())
        except AttributeError:
            print("None")
    c = 0
    while(True):
        if root.parent:
            root = root.parent
        else:
            break

Submission status: Accepted

Solution code:

class Node:
	def __init__(self, key, pri):
		self.key = key
		self.pri = pri
		self.left = self.right = None
	def __str__(self):
		ret = ''
		ret += 'key=' + str(self.key)
		ret += ',pri=' + str(self.pri)
		ret += ',left='
		if self.left != None: ret += str(self.left.key)
		ret += ',right='
		if self.right != None: ret += str(self.right.key)
		return ret

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

	def print(self):
		self.print_in_order()
		self.print_pre_order()

	def print_in_order(self):
		st = []
		cur = self.root
		while cur != None or len(st) != 0:
			if cur != None:
				st.append(cur)
				cur = cur.left
			else:
				cur = st.pop()
				print(' ' + str(cur.key), end='')
				cur = cur.right
		print()

	def print_pre_order(self):
		st = []
		st.append(self.root)
		while len(st) != 0:
			cur = st.pop()
			print(' ' + str(cur.key), end='')
			if cur.right != None:
				st.append(cur.right)
			if cur.left != None:
				st.append(cur.left)
		print()

	def find(self, key):
		cur = self.root
		while cur != None:
			if key == cur.key:
				return cur
			if key < cur.key:
				cur = cur.left
			else:
				cur = cur.right
		return None

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

	def insert_(self, node, key, pri):
		if node == None:
			return Node(key, pri)
		if key == node.key:
			return node

		if key < node.key:
			node.left = self.insert_(node.left, key, pri)
			if node.pri < node.left.pri:
				node = self.right_rotate(node)
		else:
			node.right = self.insert_(node.right, key, pri)
			if node.pri < node.right.pri:
				node = self.left_rotate(node)
		return node

	def right_rotate(self, node):
		tmp = node.left
		node.left = tmp.right
		tmp.right = node
		return tmp

	def left_rotate(self, node):
		tmp = node.right
		node.right = tmp.left
		tmp.left = node
		return tmp

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

	def delete_(self, node, key):
		if node == None:
			return node
		if key < node.key:
			node.left = self.delete_(node.left, key)
		elif key > node.key:
			node.right = self.delete_(node.right, key)
		else:
			return self.delete__(node, key)
		return node

	def delete__(self, node, key):
		if (node.left == None and node.right == None):
			return None
		elif node.left == None:
			node = self.left_rotate(node)
		elif node.right == None:
			node = self.right_rotate(node)
		else:
			if node.left.pri > node.right.pri:
				node = self.right_rotate(node)
			else:
				node = self.left_rotate(node)
		return self.delete_(node, key)

n = int(input())
treap = Treap()
for i in range(n):
	cmd = list(map(str, input().split()))
	if cmd[0] == 'print':
		treap.print()
	else:
		key = int(cmd[1])
		if cmd[0] == 'insert':
			treap.insert(key, int(cmd[2]))
		elif cmd[0] == 'find':
			if treap.find(key) != None:
				print('yes')
			else:
				print('no')
		else:
			treap.delete(key)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

class Node:
  def __init__(self, key, priority):
    self.key = key
    self.priority = priority
    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, priority):
  
  if not t: 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 not t: return None
  
  if key == t.key:
    if (not t.left) and (not t.right): return None
  elif 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 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.key == key:
    print("yes")
    return 0
  elif t.key < key and (not t.right):
    find(t.right, key)
  elif t.key > key and (not t.left):
    find(t.left, key)
  else:
    print("no")
  return 0

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

def pre_print(t):
  print(" " + str(t), end='')
  if not t.left:
    pre_print(t.left)
  if not t.right:
    pre_print(t.right)
  
Treap = None
num = int(input())
for i in range(num):
  string = list(input().split())
  if string[0] == "insert":
    key = int(string[1])
    priority = int(string[2])
    insert(Treap, key, priority)
  elif string[0] == "find":
    key = int(string[1])
    find(key)
  elif string[0] == "delete":
    key = int(string[1])
    erase(Treap, key)
  else:
    in_print(Treap)
    print()
    pre_print(Treap)
    print()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

class Node:
  def __init__(self, key, priority):
    self.key = key
    self.priority = priority
    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, priority):
  
  if not t: 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 not t: return None
  
  if key == t.key:
    if (not t.left) and (not t.right): return None
  elif 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 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.key == key:
    print("yes")
    return 0
  elif t.key < key and (not t.right):
    find(t.right, key)
  elif t.key > key and (not t.left):
    find(t.left, key)
  else:
    print("no")
  return 0

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

def pre_print(t):
  print(" " + str(t), end='')
  if not t.left:
    pre_print(t.left)
  if not t.right:
    pre_print(t.right)
  
Treap = None
num = int(input())
for i in range(num):
  string = list(input().split())
  if string[0] == "insert":
    key = int(string[1])
    priority = int(string[2])
    insert(Treap, key, priority)
  elif string[0] == "find":
    key = int(string[1])
    find(Treap, key)
  elif string[0] == "delete":
    key = int(string[1])
    erase(Treap, key)
  else:
    in_print(Treap)
    print()
    pre_print(Treap)
    print()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

class Node:
  def __init__(self, key, priority):
    self.key = key
    self.priority = priority
    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, priority):
  
  if not t: 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 not t: return None
  
  if key == t.key:
    if (not t.left) and (not t.right): return None
  elif 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 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.key == key:
    print("yes")
    return 0
  elif t.key < key and (not t.right):
    find(t.right, key)
  elif t.key > key and (not t.left):
    find(t.left, key)
  else:
    print("no")
  return 0

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

def pre_print(t):
  print(" " + str(t), end='')
  if t.left != None:
    pre_print(t.left)
  if t.right != None:
    pre_print(t.right)
  
Treap = None
num = int(input())
for i in range(num):
  string = list(input().split())
  if string[0] == "insert":
    key = int(string[1])
    priority = int(string[2])
    insert(Treap, key, priority)
  elif string[0] == "find":
    key = int(string[1])
    find(Treap, key)
  elif string[0] == "delete":
    key = int(string[1])
    erase(Treap, key)
  else:
    in_print(Treap)
    print()
    pre_print(Treap)
    print()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

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 not t: 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 not t: return None
  
  if key == t.key:
    if (not t.left) and (not t.right): return None
  elif 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 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.key == key:
    print("yes")
    return 0
  elif t.key < key and (not t.right):
    find(t.right, key)
  elif t.key > key and (not t.left):
    find(t.left, key)
  else:
    print("no")
  return 0

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

def pre_print(t):
  print(" " + str(t), end='')
  if t.left != None:
    pre_print(t.left)
  if t.right != None:
    pre_print(t.right)
  
Treap = None
num = int(input())
for i in range(num):
  string = list(input().split())
  if string[0] == "insert":
    key = int(string[1])
    priority = int(string[2])
    insert(Treap, key, priority)
  elif string[0] == "find":
    key = int(string[1])
    find(Treap, key)
  elif string[0] == "delete":
    key = int(string[1])
    erase(Treap, key)
  else:
    in_print(Treap)
    print()
    pre_print(Treap)
    print()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

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 not t: 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 not t: return None
  
  if key == t.key:
    if (not t.left) and (not t.right): return None
  elif 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 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.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), end='')
  if t.right != None:
    in_print(t.right)

def pre_print(t):
  print(" " + str(t), end='')
  if t.left != None:
    pre_print(t.left)
  if t.right != None:
    pre_print(t.right)
  
Treap = None
num = int(input())
for i in range(num):
  string = list(input().split())
  if string[0] == "insert":
    key = int(string[1])
    priority = int(string[2])
    insert(Treap, key, priority)
  elif string[0] == "find":
    key = int(string[1])
    find(Treap, key)
  elif string[0] == "delete":
    key = int(string[1])
    erase(Treap, key)
  else:
    in_print(Treap)
    print()
    pre_print(Treap)
    print()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

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 not t: 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 not t: return None
  
  if key == t.key:
    if (not t.left) and (not t.right): return None
  elif 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 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.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), end='')
  if t.right != None:
    in_print(t.right)

def pre_print(t):
  print(" " + str(t), end='')
  if t.left != None:
    pre_print(t.left)
  if t.right != None:
    pre_print(t.right)
  
Treap = None
num = int(input())
for i in range(num):
  string = list(input().split())
  if string[0] == "insert":
    key = int(string[1])
    priority = int(string[2])
    Treap = insert(Treap, key, priority)
  elif string[0] == "find":
    key = int(string[1])
    find(Treap, key)
  elif string[0] == "delete":
    key = int(string[1])
    Treap = erase(Treap, key)
  else:
    in_print(Treap)
    print()
    pre_print(Treap)
    print()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

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 not t: 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 not t: return None
  
  if key == t.key:
    if (not t.left) and (not t.right): return None
    elif 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 erase(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), end='')
  if t.right != None:
    in_print(t.right)

def pre_print(t):
  print(" " + str(t), end='')
  if t.left != None:
    pre_print(t.left)
  if t.right != None:
    pre_print(t.right)
  
Treap = None
num = int(input())
for i in range(num):
  string = list(input().split())
  if string[0] == "insert":
    key = int(string[1])
    priority = int(string[2])
    Treap = insert(Treap, key, priority)
  elif string[0] == "find":
    key = int(string[1])
    find(Treap, key)
  elif string[0] == "delete":
    key = int(string[1])
    Treap = erase(Treap, key)
  else:
    in_print(Treap)
    print()
    pre_print(Treap)
    print()

Submission status: Runtime Error

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 find(t.left, k) == 1:
        return 1
    if find(t.right, k) == 1:
        return 1
"""
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":
        #result = find(t, int(data[i][1]))
        #if result == 1:
        #print(dict)
        #result = data[i][1] in dict
        #print("result", result)
        #print("2", result == True)
        #print(data[i][1] in dict, data[i][1])
        if (data[i][1] in dict) == True:
            #print("12345")
            print("yes")
        else:
            print("no")
    else:
        t = erase(t, int(data[i][1]))
        del dict[data[i][1]]