学习笔记 - 左偏树

教练说这个不难,还比较有用,就扔给我们了 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,欢迎提问~

0%