Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ctime>
- using namespace std;
- typedef long long int64;
- typedef unsigned int uint;
- template<typename T>
- class __treap
- {
- private:
- struct node
- {
- node *left, *right;
- T value;
- int priority, wi;
- }*root;
- void rotate_right(node *&now)
- {
- node *tmp = now -> left;
- now -> left = tmp -> right;
- tmp -> right = now;
- now = tmp;
- }
- void rotate_left(node *&now)
- {
- node *tmp = now -> right;
- now -> right = tmp -> left;
- tmp -> left = now;
- now =tmp;
- }
- void erase(node *&now, T value)
- {
- if(now == NULL) return;
- if(now -> value == value)
- {
- if(now -> left == NULL)
- now = now -> right;
- else if(now -> right == NULL)
- now = now -> left;
- else
- {
- if(now -> left -> priority < now -> right -> priority)
- {
- rotate_right(now);
- erase(now -> right, value);
- }
- else
- {
- rotate_left(now);
- erase(now -> left, value);
- }
- }
- }
- else if(value < now -> value) erase(now -> left, value);
- else erase(now -> right, value);
- }
- void insert(node *&now, T &value)
- {
- if(now == NULL)
- {
- now = new node;
- now -> left = now -> right = NULL;
- now -> value = value;
- now -> priority = rand();
- }
- else if(value <= now -> value)
- {
- insert(now -> left, value);
- if(now -> left -> priority < now -> priority)
- rotate_right(now);
- }
- else
- {
- insert(now -> right, value);
- if(now -> right -> priority < now -> priority)
- rotate_left(now);
- }
- }
- bool find(node *&now, T value)
- {
- if(now == NULL) return false;
- if(now -> value == value) return true;
- if(now -> value > value) return find(now -> left, value);
- else return find(now -> right, value);
- return false;
- }
- T find_max(node *now)
- {
- while(now -> right != NULL)
- now = now -> right;
- return now -> value;
- }
- T find_min(node *now)
- {
- while(now -> left != NULL)
- now = now -> left;
- return now -> value;
- }
- void clear(node *&now)
- {
- if(now != NULL)
- {
- clear(now -> left);
- clear(now -> right);
- delete now;
- now = NULL;
- }
- }
- public:
- __treap()
- {
- root = NULL;
- }
- ~__treap()
- {
- clear(root);
- }
- void insert(T value)
- {
- insert(root, value);
- }
- void erase(T value)
- {
- erase(root, value);
- }
- bool find(T value)
- {
- return find(root, value);
- }
- T find_max()
- {
- return find_max(root);
- }
- T find_min()
- {
- return find_min(root);
- }
- };
- /**
- __treap< Type > treap; //Create
- treap.insert(x); //insert(x)
- bool IsFound = treap.find(x); //find(x)
- if(IsFound) {...}
- else {...}
- treap.erase(x); //erase(x)
- T x = treap.find_min()/find_max(); //find_max() or min()
- */
Advertisement
Add Comment
Please, Sign In to add comment