左偏树

核心:merge函数

思想:

左偏树的合并是一个递归过程,对于以 xxyy 为根的树:

如果 xxyy 二者之一为空树,则返回另一棵。

如果 xxyy 均不为空,则比较 xxyy 的权值大小。

如果 xx 的权值较大,那么就把 xx 右儿子和 yy 合并的结果作为 xx 新的右儿子,返回 xx

否则就把 xxyy 交换,继续上面的操作。

合并以后由于我们还要维护左偏性质,即:如果合并后右儿子的 disdis 大于左儿子的 disdis ,则交换左右儿子。

这便是通过左偏树来实现可并堆的模拟过程。

代码:

int merge(int x,int y)
{
    if(!x) return y;
    if(!y) return x;
    if(v[x]<v[y]) swap(x,y);
    rson[x]=merge(rson[x],y);
    if(dis[r[x]]>dis[l[x]]) swap(lson[x],rson[x]);
    dis[x]=dis[rson[x]]+1;
    return x;
}

洛谷左偏树模板代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n, m, op, x, y;
int lson[maxn], rson[maxn], dist[maxn], fa[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){ 
	return fa[x] == x ? x : fa[x] = find(fa[x]); 
}
int merge(int x, int y){
	if (!x || !y)
		return x + y;
	if (v[y] < v[x])
		swap(x, y);
	rson[x] = merge(rson[x], y);
	if (dist[lson[x]] < dist[rson[x]])
		swap(lson[x], rson[x]);
	dist[x] = dist[rson[x]] + 1;
	return x;
}
int main()
{
	dist[0] = -1;
	read(n);
	read(m);
	For(i,1,n)
		read(v[i].v), fa[i] = i, v[i].id = i;
	while (m--)
	{
		read(op);
		read(x);
		if (op == 1)
		{
			read(y);
			if (tf[x] || tf[y])
				continue;
			x = find(x);
			y = find(y);
			if (x != y)
				fa[x] = fa[y] = merge(x, y);
		}
		if (op == 2)
		{
			if (tf[x])
			{
				printf("-1\n");
				continue;
			}
			x = find(x);
			printf("%d\n", v[x].v);
			tf[x] = true;
			fa[lson[x]] = fa[rson[x]] = fa[x] = merge(lson[x], rson[x]);
			lson[x] = rson[x] = dist[x] = 0;
		}
	}
	return 0;
}