Ryan_<

可并堆与优先队列一样，都是抽象数据类型。

优先队列使用时可直接调用stl里的priority_queue

可并堆就要自己来写了，却比前者多资瓷了一个重要操作——合并（顾名思义~

为了直观维护合并操作，运用左偏树的时候会结合并查集:

fa[x]维护每个堆的根节点(在堆中,根节点有特殊意义:键值为最大/最小)

合并/删除时分别进行union/split操作.

左偏树是一种可并堆，斜堆是一种左偏树~

一篇很好的论文：

http://wenku.baidu.com/view/515f76e90975f46527d3e1d5.html

左偏树基本操作：（以大根堆为例，即树的根节点的键值最大）

struct Heap{int l,r,dist,key;}a[N];

1、合并操作：

Merge操作既包含合并两棵子树，也可合并结点，即将结点插入子树的操作与之相同
(注：单个结点也是左偏树)。这两种情况的代码实现其实是一样的。

伪代码

特殊情况：插入结点到子树中

MY CODE:

inline int merge(int x,int y)//维护大根堆 
{
        if(!x || !y) return x+y;
	if(a[x].key<a[y].key) swap(x,y);
	a[x].r=merge(a[x].r,y);
	int ls=a[x].l;
	int rs=a[x].r;
 	fa[rs]=x;//***union!
	if(a[ls].dist<a[rs].dist) swap(a[x].l,a[x].r);
	if(!a[x].r) a[x].dist=0;
	else a[x].dist=a[rs].dist+1;
	return x;
}

2、删除操作：（删除堆顶元素，即最大值或最小值）

伪代码：

My Code：

inline int Del(int x)
{
	int l=a[x].l;
	int r=a[x].r;
	fa[l]=l;fa[r]=r;//左右子树节点分别为根
	a[x].l=a[x].r=a[x].dist=0; 
	return merge(l,r);
}

3、这就不算是基本操作了：

如果要改变某结点的值，为之奈何?

要保持堆与左偏的性质，却无法像平衡树一样旋转了..
那就...先删除该结点，再把改变后的结点合并到删除后的树中~

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define mec(a,x) memset(a,x,sizeof(a))
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define MOD 1000000007//10^9+7
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int N=1e5+10;
int n,m;
int fa[N];
struct Heap{int l,r,dist,key;}a[N];
inline int find(int x){return fa[x]==x ? x:fa[x]=find(fa[x]);}
inline int merge(int x,int y)//维护大根堆 
{
	//if(!x || !y) return x+y;
	if(!x) return y;
	if(!y) return x;
	if(a[x].key<a[y].key) swap(x,y);
	a[x].r=merge(a[x].r,y);//关键啊关键
	int ls=a[x].l;
	int rs=a[x].r;
	fa[rs]=x;//Union! 
	if(a[ls].dist<a[rs].dist) swap(a[x].l,a[x].r);//注意交换的是左右子树
	if(!a[x].r) a[x].dist=0;
	else a[x].dist=a[rs].dist+1;
	return x;
}
inline int delmax(int x)
{
	int l=a[x].l;
	int r=a[x].r;
	fa[l]=l;fa[r]=r;
	a[x].l=a[x].r=a[x].dist=0; 
	return merge(l,r);
}
inline void solve(int x,int y)
{
	a[x].key/=2;
	a[y].key/=2;
	int newx=delmax(x);
	int newy=delmax(y);
	newx=merge(newx,x);newy=merge(newy,y);
	int ret=merge(newx,newy);
	printf("%d\n",a[ret].key);
}
int main()
{
//	freopen("hdu1512.txt","r",stdin);
	while(scanf("%d",&n)!=EOF){
		F(i,1,n){
			a[i].key=read();
			a[i].l=a[i].r=a[i].dist=0;
			fa[i]=i;
		}
		m=read();
		while(m--){
			int x,y;
			x=read();y=read();
			int fx=find(x);
			int fy=find(y);
			if(fx==fy) puts("-1");
			else solve(fx,fy);
		}
	}
	return 0;
}
	

【反思】

M67说：得意之时就是你灭亡之日

WA是因为忘了有多组数据..

补充：