左偏树(可并堆)


左偏树

扒来的标准说明

左偏树(Leftist Tree)是一种可并堆(Mergeable Heap) ,它除了支持优先队列的三个基本操作(插入,删除堆顶,取最小节点),还支持一个很特殊的操作————合并操作。
左偏树是一棵二叉树,具有堆的性质,同时具有左偏性质
它有以下属性与定义
键值(key):用于节点比较大小的属性,类似于堆中节点的键值
外节点:左子树或右子树为空的节点称为外节点,左子树和右子树可以同时为空。所以叶子节点必是外节点,定义外节点的距离值为0,空节点的距离值为-1。
距离(dis):一个不是外节点的点的距离定义为其到子树中最近的外节点的距离
左右子树均不为空的节点不是外节点。左偏数的距离定义数中根节点的距离。左偏树的深度和距离无必然联系,一颗向左偏的链也是左偏树,其距离为0,深度为n
如下图所示为一颗左偏树。
左偏树(可并堆)
数字为距离
左孩子的dis /(/ge/) 右孩子的dis 即左偏性质

操作

合并
因为树是左偏的,同时为了不让树的深度太深,所以合并时要把另一棵树接在原树的右子树上
代码:

int merge(int u,int v)// 合并
{
	if(!u||!v)	return u+v;// 若有一颗左偏树为空,直接加
	if(heap[u]==heap[v]?u>v:heap[u]>heap[v])	swap(u,v);
	rs[u]=merge(rs[u],v);// 要满足堆的性质
	if(dis[ls[u]]<dis[rs[u]])	swap(ls[u],rs[u]);// 维护左偏性质
	fa[ls[u]]=fa[rs[u]]=fa[u]=u;// 更新父节点
	dis[u]=dis[rs[u]]+1;// 更新dis距离
	return u;// 返回根节点
}

插入
将单个节点视为一个堆,合并即可


弹出
合并根节点的左右孩子即可
代码:

void pop(int u)
{
	del[u]=true;
	fa[ls[u]]=ls[u];
	fa[rs[u]]=rs[u];
	fa[u]=merge(ls[u],rs[u]);
}

左偏树也有加或乘的操作,但本人能力有限,以后会了再来填坑

例题

P3377 【模板】左偏树(可并堆)
代码:

#include<iostream>
#include<cstdio>
typedef long long ll;
using namespace std;
inline ll read()
{
	ll x=0;
	bool fg=false;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		fg|=(ch=='-');
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return fg?~x+1:x;
}
const int N=1e5+5;
int n,m;
int fa[N],ls[N],rs[N];
ll dis[N],heap[N];
bool del[N];
int found(int x)
{
	return fa[x]==x?fa[x]:fa[x]=found(fa[x]);
}
int merge(int u,int v)// 合并
{
	if(!u||!v)	return u+v;// 若有一颗左偏树为空,直接加
	if(heap[u]==heap[v]?u>v:heap[u]>heap[v])	swap(u,v);
	rs[u]=merge(rs[u],v);// 要满足堆的性质
	if(dis[ls[u]]<dis[rs[u]])	swap(ls[u],rs[u]);// 维护左偏性质
	fa[ls[u]]=fa[rs[u]]=fa[u]=u;// 更新父节点
	dis[u]=dis[rs[u]]+1;// 更新dis距离
	return u;// 返回根节点
}
void pop(int u)
{
	del[u]=true;
	fa[ls[u]]=ls[u];
	fa[rs[u]]=rs[u];
	fa[u]=merge(ls[u],rs[u]);
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;++i)
		heap[i]=read(),fa[i]=i;
	for(int i=1;i<=m;++i)
	{
		int op=read(),x,y;
		if(op==1)
		{
			x=read(),y=read();
			if(del[x]||del[y])	continue;
			x=found(x),y=found(y);
			if(x!=y)	fa[x]=fa[y]=merge(x,y);
		}
		else
		{
			x=read();
			if(del[x])	printf("-1/n");
			else
			{
				x=found(x);
				printf("%lld/n",heap[x]);
				pop(x);
			}
		}
	}
	return 0;
}

原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/279539.html

(0)
上一篇 2022年8月8日
下一篇 2022年8月8日

相关推荐

发表回复

登录后才能评论