Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <time.h>
- #include <stdlib.h>
- #include <stdio.h>
- const int MAXN = 1000010; //1e6
- struct node {
- int key, prio;
- node *ch[2];
- } base[MAXN], *top, *root, *null, nil;
- typedef node* tree;
- inline tree newNode(int key) {
- static int seed = 3312;
- top -> key = key; top -> prio = seed = int((seed * 48271LL) & 2147483647);
- top -> ch[0] = top -> ch[1] = null;
- return top++;
- }
- inline void Rotate(tree &x, int d) {
- tree y = x -> ch[!d];
- x -> ch[!d] = y -> ch[d];
- y -> ch[d] = x;
- x = y;
- }
- void Insert(tree &t, int key) {
- if(t == null) t = newNode(key);
- else
- {
- int d = t -> key < key;
- Insert(t -> ch[d], key);
- if(t -> ch[d] -> prio < t -> prio) Rotate(t, !d);
- }
- }
- //assuming the key exists in the set
- void Delete(tree &t, int key) {
- if (t -> key != key) {
- Delete(t -> ch[t -> key < key], key);
- }
- else if(t -> ch[0] == null) t = t -> ch[1];
- else if(t -> ch[1] == null) t = t -> ch[0];
- else {
- int d = t -> ch[0] -> prio < t -> ch[1] -> prio;
- Rotate(t, d);
- Delete(t -> ch[d], key);
- }
- }
- int main()
- {
- srand(time(0));
- const int n = 1000000; //1e6
- null = &nil;
- top = base;
- root = newNode(0); //dummy new root
- clock_t t0 = clock();
- for(int i = 0; i < n; ++i)
- {
- Insert(root, rand()); //rand key insert
- }
- printf("Time: %f\n", ((float)clock() - t0) / CLOCKS_PER_SEC);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement