SHARE
TWEET

Untitled

a guest May 24th, 2019 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2. import java.lang.*;
  3.  
  4. class Main {
  5.  
  6.     public static void main(String[] args) {
  7.         new Main().solve();
  8.     }
  9.  
  10.     public void solve() {
  11.         Scanner scanner = new Scanner(System.in);
  12.         int numOps = scanner.nextInt();
  13.         int key, pri;
  14.         Node root = null;
  15.  
  16.         for(int i = 0; i < numOps; i++) {
  17.             String op = scanner.next();
  18.  
  19.             if(op.equals("insert")) {
  20.                 key = scanner.nextInt();
  21.                 pri = scanner.nextInt();
  22.                 root = insert(root, key, pri);
  23.             } else if(op.equals("find")) {
  24.                 key = scanner.nextInt();
  25.                 System.out.println(find(root, key) ? "yes" : "no");
  26.             } else if(op.equals("delete")) {
  27.                 key = scanner.nextInt();
  28.                 root = erase(root, key);
  29.             } else if(op.equals("print")) {
  30.                 printTreap(root);
  31.             }
  32.         }
  33.     }
  34.  
  35.     public Node rightRotate(Node t) {
  36.         Node s = t.left;
  37.         t.left = s.right;
  38.         s.right = t;
  39.         return s;
  40.     }
  41.  
  42.     public Node leftRotate(Node t) {
  43.         Node s = t.right;
  44.         t.right = s.left;
  45.         s.left = t;
  46.         return s;
  47.     }
  48.  
  49.     public Node insert(Node t, int key, int pri) {
  50.         if(t == null)
  51.             return new Node(key, pri);
  52.  
  53.         if(key == t.key)
  54.             return t;
  55.  
  56.         if(key < t.key) {
  57.             t.left = insert(t.left, key, pri);
  58.             if(t.pri < t.left.pri)
  59.                 t = rightRotate(t);
  60.         } else {
  61.             t.right = insert(t.right, key, pri);
  62.             if(t.pri < t.right.pri)
  63.                 t = leftRotate(t);
  64.         }
  65.  
  66.         return t;
  67.     }
  68.  
  69.     public Node erase(Node t, int key) {
  70.         if(t == null)
  71.             return null;
  72.  
  73.         if(key == t.key) {
  74.             if(t.left == null && t.right == null)
  75.                 return null;
  76.             else if(t.left == null)
  77.                 t = leftRotate(t);
  78.             else if(t.right == null)
  79.                 t = rightRotate(t);
  80.             else {
  81.                 if(t.left.pri > t.right.pri)
  82.                     t = rightRotate(t);
  83.                 else
  84.                     t = leftRotate(t);
  85.             }
  86.  
  87.             return erase(t, key);
  88.         }
  89.  
  90.         if(key < t.key)
  91.             t.left = erase(t.left, key);
  92.         else
  93.             t.right = erase(t.right, key);
  94.  
  95.         return t;
  96.     }
  97.  
  98.     public boolean find(Node root, int target) {
  99.         if(root == null)
  100.             return false;
  101.  
  102.         if(root.key == target)
  103.             return true;
  104.         else if(root.key < target)
  105.             return find(root.right, target);
  106.         else
  107.             return find(root.left, target);
  108.     }
  109.  
  110.     public void printTreap(Node root) {
  111.         inorderTraverse(root);
  112.         System.out.println();
  113.         preorderTraverse(root);
  114.         System.out.println();
  115.     }
  116.  
  117.     private void inorderTraverse(Node root) {
  118.         if(root != null) {
  119.             inorderTraverse(root.left);
  120.             System.out.print(" " + root.key);
  121.             inorderTraverse(root.right);
  122.         }
  123.     }
  124.  
  125.     private void preorderTraverse(Node root) {
  126.         if(root != null) {
  127.             System.out.print(" " + root.key);
  128.             preorderTraverse(root.left);
  129.             preorderTraverse(root.right);
  130.         }
  131.     }
  132.  
  133.     class Node {
  134.         int key;
  135.         int pri;
  136.         Node left;
  137.         Node right;
  138.  
  139.         public Node(int k, int p) {
  140.             key = k;
  141.             pri = p;
  142.             left = null;
  143.             right = null;
  144.         }
  145.     }
  146. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top