学习笔记 - 左偏树 | Lucky_Glass's Blog

以心为名，名为爱惜

0%

学习笔记 - 左偏树

发表于 更新于 分类于 Valine：

教练说这个不难，还比较有用，就扔给我们了 awa

Part1. 可并堆

顾名思义，可并堆是一种支持合并操作的堆。它支持：

  1. 快速查询最小值/最大值（要么是大根堆，要么是小根堆）
  2. 插入一个元素
  3. 删除堆顶
  4. 合并两个堆

下面引入的左偏树是可并堆的一种实现方式，各操作的时间复杂度为：

  1. 查询最值，即堆顶：$O(1)$；
  2. 插入元素 $O(\log n)$；
  3. 删除堆顶 $O(\log n)$；
  4. 合并堆 $O(\log n)$；

Part2. 左偏树

左偏树是一种满足堆性质的二叉树。（以下均默认为大根堆）

Part2/1. 左偏性质

称一个没有左儿子或右儿子的节点 u 为 “外节点”；反之则为内节点。
对于外节点，定义其“距离”为 $0$；对于内节点，定义它的距离为 在它的子树中，与它最近的外节点的距离。

左偏树满足左偏性质：

对于任意节点，满足左儿子的距离大于等于右儿子的距离（或者右儿子为空）。

举个例子，一个左偏树可能长这样：

png1

但是下面就不是左偏树（节点上的标号是“距离”）：

png2

Part2/2. 求距离

因为右儿子的距离一定小于左儿子的距离，所以如果一个节点不是外节点，那么它的距离 dis[u] 其实就是 dis[rch[u]]。

因此，根节点的距离不会超过 $\left\lfloor \log (n+1)\right\rfloor-1$。

Part2/3. 合并操作

【定义】

key[u] u的键值；dis[u] u的距离；

假设合并的两个堆的根分别是 A,B，不妨设 key[A]>key[B]，则把 B 插入到 A 的右子树。如果右子树为空，就直接把 B 插入到 A 的右儿子处。

然后发现 A 的左儿子的距离可能比右儿子小了，我们可以交换 A 的左右儿子来维护左偏性质。

最后更新节点距离就好了。（其实这是一个递归的过程）

1
2
3
4
5
6
7
8
Merge(A,B)
	if A==NULL then return B
	if B==NULL then return A
	if key[A]<key[B] then swap(A,B)
	rch[A] <- Merge(rch[A],B)
	if dis[lch[A]]<dis[rch[A]] then swap(lch[A],rch[A])
	dis[A] <- dis[rch[A]]+1
	return A

上面 Merge() 的返回值是合并后的根节点。

Part2/4. 其他操作

  • 插入元素：把单个元素当成一个堆，与原堆合并
  • 删除堆顶：合并堆顶的左子树和右子树

Part3. 源代码

参考题目：洛谷 左偏树模板

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=100000;

int n,m;
int Ia[N+3];
bool Bdel[N+3];

struct MERGESET{
	int Mpre[N+3],Mtag[N+3];
	void Init(int Nn){
		for(int i=1;i<=Nn;i++){
			Mpre[i]=i;
			Mtag[i]=0;
		}
	}
	int FindPre(int Pu){return Mpre[Pu]=Mpre[Pu]==Pu? Pu:FindPre(Mpre[Pu]);}
	bool Merge(int Pu,int Pv){
		int Qu=FindPre(Pu),Qv=FindPre(Pv);
		if(Qu==Qv) return false;
		Mpre[Qu]=Qv;
		return true;
	}
	void Modify(int Pu,int Vx){
		int Qu=FindPre(Pu);
		Mtag[Qu]=Vx;
	}
}Mset;
struct LHEAP{
	struct HNODE{int ch[2],key,tim,dis;}Hnod[N+3];
	friend bool operator <(const HNODE A,const HNODE B){
		if(A.key==B.key) return A.tim<B.tim;
		return A.key<B.key;
	}
	int Hrt[N+3];
	LHEAP(){
		Hnod[0].dis=-1;Hnod[0].key=(1<<29);
	}
	void NewHeap(int id,int Vv,int Vtim){
		Hrt[id]=id;
		Hnod[id].ch[0]=Hnod[id].ch[1]=Hnod[id].dis=0;
		Hnod[id].key=Vv;Hnod[id].tim=Vtim;
	}
	void PushUp(int Pu){
		if(Hnod[Hnod[Pu].ch[0]].dis<Hnod[Hnod[Pu].ch[1]].dis)
			swap(Hnod[Pu].ch[0],Hnod[Pu].ch[1]);
		Hnod[Pu].dis=Hnod[Hnod[Pu].ch[1]].dis+1;
	}
	int Merge(int Pu,int Pv){
		if(!Pu) return Pv;
		if(!Pv) return Pu;
		if(Hnod[Pv]<Hnod[Pu]) swap(Pu,Pv);
		Hnod[Pu].ch[1]=Merge(Hnod[Pu].ch[1],Pv);
		PushUp(Pu);
		return Pu;
	}
	void Delete(int id){
		Bdel[Hrt[id]]=true;
		Hrt[id]=Merge(Hnod[Hrt[id]].ch[0],Hnod[Hrt[id]].ch[1]);
		Mset.Modify(Hrt[id],Hrt[id]);
	}
}Hhep;

int main(){
	scanf("%d%d",&n,&m);
	Mset.Init(n);
	for(int i=1;i<=n;i++){
		int Ii;scanf("%d",&Ii);
		Ia[i]=Ii;
		Hhep.NewHeap(i,Ii,i);
		Mset.Modify(i,i);
	}
	for(int i=1;i<=m;i++){
		int Itmp;scanf("%d",&Itmp);
		if(Itmp==1){
			int Iu,Iv;scanf("%d%d",&Iu,&Iv);
			if(Bdel[Iu] || Bdel[Iv]) continue;
			int Pu=Mset.Mtag[Mset.FindPre(Iu)],Pv=Mset.Mtag[Mset.FindPre(Iv)];
			if(Mset.Merge(Iu,Iv)){
				int Rr=Hhep.Merge(Pu,Pv);
				Mset.Modify(Pu,Rr);
			}
		}
		else{
			int Iu;scanf("%d",&Iu);
			if(Bdel[Iu]){
				printf("-1\n");
				continue;
			}
			int Pu=Mset.Mtag[Mset.FindPre(Iu)];
			printf("%d\n",Ia[Pu]);
			Hhep.Delete(Pu);
		}
	}
	return 0;
}

另外是指针版的，就直接打包成 struct 了：

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
struct LHEAP{
	struct HNODE{
		int key,dis;
		HNODE *ch[2];
		bool operator <(const HNODE B)const{return key<B.key;}
	}Hnod[N+3];
	HNODE *Hrt[N+3],*Hcnt,*NIL;
	LHEAP(){
		NIL=Hcnt=Hnod;
		NIL->ch[0]=NIL->ch[1]=NIL;
		NIL->dis=-1;
	}
	void PushUp(HNODE *Pu){
		if(Pu->ch[0]->dis<Pu->ch[1]->dis) swap(Pu->ch[0],Pu->ch[1]);
		Pu->dis=Pu->ch[1]->dis+1;
	}
	HNODE *NewNode(int Vv){
		HNODE *P=++Hcnt;
		P->ch[0]=P->ch[1]=NIL;
		P->key=Vv;P->dis=0;
	}
	HNODE *Merge(HNODE *Pu,HNODE *Pv){
		if(Pu==NIL) return Pv;
		if(Pv==NIL) return Pu;
		if(Pv<Pu) swap(Pu,Pv);
		Pu->ch[1]=Merge(Pu->ch[1],Pv);
		PushUp(Pu);
		return Pu;
	}
	void NewHeap(int id,int Vv){
		Hrt[id]=NewNode(Vv);
	}
	void Delete(int id){
		Hrt[id]=Merge(Hrt[id]->ch[0],Hrt[id]->ch[1]);
	}
};

The End

Thanks for reading!

Email: lucky_glass@foxmail.com，欢迎提问~