左偏树(可并堆)

cnblogs 2024-08-08 14:39:00 阅读 78

一种支持修改的数据结构

左偏树(可并堆)

定义

在这之前,我们先来阐述一些定义:

  1. 节点\(ls\)\(rs\) 为空的节点
  2. 距离:节点的距离 \(dist_x\) 定义为节点 \(x\) 到距 \(x\) 最近的外节点的距离,空节点的距离为 \(-1\)

其次是左偏树的性质:

  1. 左偏性:即满足 \(dist_{ls}>=dist_{rs}\)
  2. 堆性质:若满足小根堆,则满足 \(v_x<=v_{ls}\) , \(v_x<=v_{rs}\)

这引出了左偏树的一些结论:

  1. 节点 \(x\) 的距离为 \(dist_{rs}+1\) (由于左偏性)
  2. 距离为 \(n\) 的左偏树至少有 \(2^n-1\) 个节点,最少时,形态接近满二叉树
  3. \(n\) 的节点的左偏树的根节点距离是 \(O(log_2n)\)

接下来是左偏树支持的一些操作:

  1. 合并
  2. 插入给定值
  3. 求最小值
  4. 删除最小值
  5. 求指定节点在左偏树的根节点

详解

一.合并

\(merge(x,y)\) 为合并以 \(x\) , \(y\) 为根节点的两棵子树,返回值为合并后的根节点。

先考虑堆的合并:

  1. \(v_x<=v_y\) ,则以 \(x\) 做为合并后的根节点。(若有 \(v_x>v_y\)\(swap(x,y)\) )
  2. \(y\)\(x\) 的一个儿子合并,合并后的根节点代替与 \(y\) 合并的儿子的位置,返回 \(x\)
  3. 重复以上操作,直到 \(x\)\(y\) 有一方是空节点。

然鹅,这样合并的操作复杂度为 \(O(h)\) \(h\) 为树高,当堆退化为链时,复杂度为 \(O(n)\) ,想要进一步优化,则要优化左偏树。由于在左偏树中,左儿子的距离大于右儿子的距离,所以每次选择右儿子进行合并,则单次复杂度可以来到 \(O(long_2n)\) ;

但两棵树合并后可能破坏左偏树的左偏性,故在每次合并后,判断节点 \(x\) 是否符合 \(dist_{ls}>=dist_{rs}\) ,若不满足则 \(swap(ls,rs)\) ,并维护 \(dist_x=dist_{rs}+1\) ,即可维护左偏树的左偏性。

二.插入给定值

新建一个值等于插入值的点,将该节点与左偏树合并即可。

三.求最小值

由于左偏树的堆性质,所以左偏树的最小值即为左偏树的根节点的值。

四.删除最小值

等价于删除左偏树的根节点,合并左右子树即可。

五.求指定节点在左偏树的根节点

可以记录每个节点的父亲节点,然后暴力跳父亲节点。

<code>int find(int x){

if(rt[x]) return find(rt[x]);

return x;

}

是不是非常熟悉,当然,可以使用路径压缩优化。

int find(int x){

if(rt[x]) return rt[x]=find(fa[x]);

return x;

}

如此,我们便需维护 \(rt\) 数组。在合并两个节点时,令:

rt[x]=rt[y]=merge(x,y);

在删除左偏树的最小值时

rt[ls[x]]=rt[rs[x]]=rt[x]=merge(ls[x],rs[x]);

因为 \(x\) 之前靠近根节点,在路径压缩时,\(rt\) 数组有可能等于 \(x\) ,所以 \(rt[x]\) 也指向删除后的根节点。

由于使用了路径压缩优化,导致 \(x\) 的树形结构被破坏,若之后还需使用 \(x\) 则需重建一个同值节点。使用路径压缩优化后,可以在 \(O(log_2n)\) 的时间复杂度内找到一个点在左偏树的根节点。

完整代码

#include <bits/stdc++.h>

#define seq(q, w, e) for (int q = w; q <= e; q++)

#define ll long long

using namespace std;

const int maxn = 1e5+10;

int m,n,x,y,op;

int ls[maxn],rs[maxn],dist[maxn],rt[maxn];

bool tf[maxn];

struct node{ //点节点结构体

int id,v; //编号,价值

bool operator<(node x)const{return v==x.v?id<x.id:v<x.v;}

}v[maxn];

int find(int x){ //寻找祖宗

if(rt[x]==x)

return x;

return rt[x]=find(rt[x]); //路径压缩

}

int merge(int x,int y){ //合并x,y

if(!x||!y) //若这两个节点中存在空节点

return x+y;

if(v[y]<v[x]) //保证v[x]<v[y]

swap(x,y);

rs[x]=merge(rs[x],y); //由于左偏性质,最优合右树

if(dist[ls[x]]<dist[rs[x]]) //维护左偏性质

swap(ls[x],rs[x]);

dist[x]=dist[rs[x]]+1; //维护根节点距离

return x;

}

signed main()

{

ios::sync_with_stdio(0);

cin.tie(0);cout.tie(0);

dist[0]=-1;

cin>>n>>m;

seq(i,1,n){ //初始化

cin>>v[i].v; //输入价值

rt[i]=i;

v[i].id=i;

}

while(m--){

cin>>op>>x;

if(op==1){

cin>>y;

if(tf[x]||tf[y]) continue;

x=find(x);y=find(y);

if(x!=y) rt[x]=rt[y]=merge(x,y); //若不在一棵树上

}

else{

if(tf[x]){

cout<<"-1"<<"\n";

continue;

}

x=find(x);

cout<<v[x].v<<"\n";

tf[x]=true;

rt[ls[x]]=rt[rs[x]]=rt[x]=merge(ls[x],rs[x]);

ls[x]=rs[x]=dist[x]=0;

}

}

return 0;

}


上一篇: 【C++】C++前言

下一篇: C++中resize()使用详解

本文标签

学习笔记   


声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。