3
16
2016
0

左偏树学习笔记~

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

优先队列使用时可直接调用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、这就不算是基本操作了:

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

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

模板题:  
hdu1512 & zoj2334Monkey King
 
【题意】有n个猴子,一开始每个猴子只认识自己。每个猴子有一个力量值,力量值越大表示这个猴子打架越厉害。如果2个猴子不认识,他们就会找他们认识的猴子中力量最大的出来单挑,单挑不论输赢,单挑的2个猴子力量值减半,这2拨猴子就都认识了,不打不相识嘛。现在给m组询问,如果2只猴子相互认识,输出-1,否则他们各自找自己认识的最牛的猴子单挑,求挑完后这拨猴子力量最大值。
 
【分析】判断两个猴子是否认识显然要用并查集,可怎么维护每个猴子的力量值/查询认识的猴子里力量值最大的呢?
就要用到可并堆了.每次又是取每个堆的最大值,就维护大根堆咯.
My Code:(包含上述几种操作)
 
#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是因为忘了有多组数据..

 

补充:

Category: 可并堆 | Tags: 并查集 左偏树 学习笔记 | Read Count: 393

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com