3481_treap.cpp

一个数据结构的程序

#include <iostream>
#include <cstdio>
using namespace std;
const int M=1000001;

struct node{
	int l,r,key,prio;
};

int root,size;
node tree[M];
int root1,size1;
node tree1[M];

void rot_l(int &x)
{
	int y=tree[x].r;
	tree[x].r=tree[y].l;
	tree[y].l=x;
	x=y;
}

void rot_r(int &x)
{
	int y=tree[x].l;
	tree[x].l=tree[y].r;
	tree[y].r=x;
	x=y;
}

void insert(int &x,int k,int p)
{
	if(x==-1)
	{
		x=++size;
		tree[x].l=tree[x].r=-1;
		tree[x].key=k;tree[x].prio=p;
	}
	else if(k<tree[x].key)
	{
		insert(tree[x].l,k,p);
		if(tree[x].prio<tree[tree[x].l].prio)
			rot_r(x);
	}
	else
	{
		insert(tree[x].r,k,p);
		if(tree[x].prio<tree[tree[x].r].prio)
			rot_l(x);
	}
}

void remove(int &x,int k)
{
	if(x==-1)
		return ;
	if(k<tree[x].key)
		remove(tree[x].l,k);
	else if(k>tree[x].key)
		remove(tree[x].r,k);
	else
	{
		if(tree[x].l==-1&&tree[x].r==-1)
			x=-1;
		else if(tree[x].l==-1)
			x=tree[x].r;
		else if(tree[x].r==-1)
			x=tree[x].l;
		else
		{
			if(tree[tree[x].l].prio<tree[tree[x].r].prio)
			{
				rot_l(x);
				remove(tree[x].l,k);
			}
			else
			{
				rot_r(x);
				remove(tree[x].r,k);
			}
		}
	}
}
void rot_l1(int &x)
{
	int y=tree1[x].r;
	tree1[x].r=tree1[y].l;
	tree1[y].l=x;
	x=y;
}

void rot_r1(int &x)
{
	int y=tree1[x].l;
	tree1[x].l=tree1[y].r;
	tree1[y].r=x;
	x=y;
}

void insert1(int &x,int k,int p)
{
	if(x==-1)
	{
		x=++size1;
		tree1[x].l=tree1[x].r=-1;
		tree1[x].key=k;tree1[x].prio=p;
	}
	else if(k<tree1[x].key)
	{
		insert1(tree1[x].l,k,p);
		if(tree1[x].prio>tree1[tree1[x].l].prio)
			rot_r1(x);
	}
	else
	{
		insert1(tree1[x].r,k,p);
		if(tree1[x].prio>tree1[tree1[x].r].prio)
			rot_l1(x);
	}
}

void remove1(int &x,int k)
{
	if(x==-1)
		return ;
	if(k<tree1[x].key)
		remove1(tree1[x].l,k);
	else if(k>tree1[x].key)
		remove1(tree1[x].r,k);
	else
	{
		if(tree1[x].l==-1&&tree1[x].r==-1)
			x=-1;
		else if(tree1[x].l==-1)
			x=tree1[x].r;
		else if(tree1[x].r==-1)
			x=tree1[x].l;
		else
		{
			if(tree1[tree1[x].l].prio>tree1[tree1[x].r].prio)
			{
				rot_l1(x);
				remove1(tree1[x].l,k);
			}
			else
			{
				rot_r1(x);
				remove1(tree1[x].r,k);
			}
		}
	}
}

int main()
{
	int cmd,a,b;
	root=root1=-1;
	size=size1=-1;
	while(1)
	{
		scanf("%d",&cmd);
		if(cmd==0)
			break;
		if(cmd==1)
		{
			scanf("%d %d",&a,&b);
			insert(root,a,b);
			insert1(root1,a,b);
		}
		else if(cmd==2)
		{
			if(root==-1)
				printf("0\n");
			else
			{
				printf("%d\n",tree[root].key);
				remove1(root1,tree[root].key);
				remove(root,tree[root].key);
			}
		}
		else
		{
			if(root1==-1)
				printf("0\n");
			else
			{
				printf("%d\n",tree1[root1].key);
				remove(root,tree1[root1].key);
				remove1(root1,tree1[root1].key);
			}
		}
	}
	return 0;
}