裸treap...
學(xué)會(huì)了刪除..
orz..
#include <iostream>
//#include <fstream>
using namespace std;
//ifstream fin("t3481.in");
const int MAXN=100000;
const int INF=0x7fffffff;
int len=0;
struct node
{
node *left,*right;
int key,r_key,value;
}*root,tree[MAXN];
/**//*
a
/ \
c b
/ \ / \
g fd e
*/
void RotateLeft(node *&x)
{
node *z=x->right;
x->right=z->left;
z->left=x;
x=z;
}
void RotateRight(node *&x)
{
node *z=x->left;
x->left=z->right;
z->right=x;
x=z;
}
void insert(node *&x,int value,int key)
{
if (NULL==x)
{
node *p=&tree[len++];
p->left=NULL;
p->right=NULL;
p->key=key;
p->value=value;
p->r_key=rand();
x=p;
return;
}
if (x->key<=key)
{
insert(x->right,value,key);
if (x->r_key>x->right->r_key) RotateLeft(x);
}
else
{
insert(x->left,value,key);
if (x->r_key>x->left->r_key) RotateRight(x);
}
}
void _delete(node *&x,int key)
{
if (x==NULL) return;
if (x->key>key) _delete(x->left,key);
else
if (x->key<key) _delete(x->right,key);
else
{
if (x->left==NULL&&x->right==NULL)
{
x=NULL;
return;
}
else
{
int ll,rr;
ll=x->left==NULL?INF:x->left->r_key;
rr=x->right==NULL?INF:x->right->r_key;
if (ll<rr)
{
RotateRight(x);
}
else
{
RotateLeft(x);
}
_delete(x,key);
}
}
}
void find_max(node *x)
{
if (NULL==x) {cout<<0<<endl;return;}
if (x->right!=NULL)
{
find_max(x->right);
}
else
{
cout<<x->value<<endl;
_delete(root,x->key);
return;
}
}
void find_min(node *x)
{
if (NULL==x) {cout<<0<<endl;return;}
if (x->left!=NULL)
{
find_min(x->left);
}
else
{
cout<<x->value<<endl;
_delete(root,x->key);
return;
}
}
int edit;
int main()
{
root=NULL;
while(1)
{
int x,y;
cin>>edit;
if (0==edit) break;
switch(edit)
{
case 1:cin>>x>>y;insert(root,x,y);break;
case 2:find_max(root);break;
case 3:find_min(root);break;
default:break;
}
}
//system("pause");
return 0;
}