【学习笔记】左偏树（可并堆）

发表于 | 分类于 | 误人子弟 个
字数统计: 656 | 阅读时长 ≈ 3

概念与基本性质

左偏树(Leftist Tree)是一种可并堆的实现，是具有左偏性质的堆有序二叉树

  • 可并堆(Mergeable Heap)是一种抽象数据类型，它除了支持优先队列的三个基本操作(Insert, Minimum,Delete-Min)，还支持一个额外的操作——合并操作。

  • 左偏性质是为了使我们可以以更小的代价在优先队列的其它两个基本操作（插入节点、删除最小节点）进行后维持堆性质。

左偏树是一棵二叉树，它的节点除了和二叉树的节点一样具有左右子树指针(left, right)外，还有两个属性，键值(key)和距离(dist)
节点的键值小于或等于它的左右子节点的键值（小根）
节点的左子节点的距离不小于右子节点的距离（左偏性质）
节点的距离等于它的右子节点的距离加1

执行操作

  1. 合并 - merge
  2. 查询堆最小值 - find
  3. 删除（并于查询） - erase

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<cstdio>
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define ll long long
using namespace std;
const int N=101000;
struct Leftist{
	int lch,rch,key,fa,dist;
}h[N];
int n,m;
inline ll read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0' or ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' and ch<='9'){x=10*x+ch-'0';ch=getchar();}
	return x*f;
}
inline void swap(int &x,int &y){int tmp=x;x=y;y=tmp;}
inline int merge(int u,int v){       //合并操作
	if(!u or !v) return u+v;
	if(h[u].key>h[v].key or (h[u].key==h[v].key and u>v)) swap(u,v);
	int &ul=h[u].lch,&ur=h[u].rch;
	ur=merge(ur,v);
	h[ur].fa=u;
	if(h[ul].dist<h[ur].dist) swap(ul,ur);
	h[u].dist=h[ur].dist+1;
	return u;
}
inline void erase(int u){     //删除操作
	int ul=h[u].lch,ur=h[u].rch;
	h[u].key=-1;h[ul].fa=0;h[ur].fa=0;
	merge(ul,ur);
}
inline int find(int x){         //查询操作
	return h[x].fa?find(h[x].fa):x;
}
int main(){
	n=read(),m=read();
	h[0].dist=-1;
	rep(i,1,n)
		h[i].key=read();
	rep(i,1,m){
		int opt,x,y;
		opt=read(),x=read();
		switch(opt){
			case 1:{
				y=read();
				if(h[x].key!=-1 && h[y].key!=-1){
					int p=find(x),q=find(y);
					if(p!=q) merge(p,q);
				}
				break;
			}
			case 2:{
				if(h[x].key==-1) printf("-1\n");
				else{
					int p=find(x);
					printf("%d\n",h[p].key);
					erase(p);
				}
				break;
			}
		}
	}
	return 0;
}

题目来源

洛谷 P3377 【模板】左偏树（可并堆）

0%