简介

对于一个数据结构，我们需要知道这东西是用来做什么的，效率怎么样。左偏树是一种支持在 $O (\log n)$ 的时间复杂度内进行合并查询的类堆式（本来就含并查集）数据结构。

支持的操作

插入一个新堆 $O (1)$ 。
合并两个堆 $O (\log n)$ 。
查询一个堆里的最值 $O (1)$ 。
删除一个堆里的最小、大值。

满足的基本性质

左偏树具有 堆性质 ，即若其满足小根堆的性质，则对于每个结点 $x$ ，有 $v_{x} \leq v_{l c}, v_{x} \leq v_{r c}$ 。
左偏树具有 左偏性质 ，即对于每个结点 $x$ ,有 $d i s t_{l c} \geq d i s t_{r c}$ 。

核心操作：合并操作

其实需要的函数就这么一个。
定义 $m e r g e (x, y)$ 为合并两棵分别以 $x, y$ 为根节点的左偏树，其返回值为合并之后的根节点。
首先不考虑左偏性质，我们描述一下合并两个具有堆性质的树的过程。假设我们要合并的是小根堆。
1.若 $v_{x} \leq v_{y}$ 则将 $x$ 作为根节点，否则交换 $x, y$ 。
2.向下递归使 $y$ 与 $x$ 的右儿子合并，并返回新儿子节点的编号。
3.当 $x$ 或 $y$ 之中有空节点时，返回 $x + y$ （避免分类讨论）。

int merge(int x, int y)
{
	if(!x || !y) return x + y;
	if(cmp(y, x)) swap(x, y);
	r[x] = merge(r[x], y);
	if(dist[r[x]] > dist[l[x]]) swap(l[x], r[x]);
	dist[x] = dist[r[x]] + 1;
	return x;
}

例题Acwing2714. 左偏树

$l u o g u$ 的例题太 $l a r g e$ 了

#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
int n;
int v[N], dist[N], l[N], r[N];
int p[N];
bool cmp(int x, int y)
{
	if(v[x] != v[y]) return v[x] < v[y];
	return x < y;
}
int find(int x)
{
	if(p[x] != x) return p[x] = find(p[x]);
	return p[x];
}
int merge(int x, int y)
{
	if(!x || !y) return x + y;
	if(cmp(y, x)) swap(x, y);
	r[x] = merge(r[x], y);
	if(dist[r[x]] > dist[l[x]]) swap(l[x], r[x]);
	dist[x] = dist[r[x]] + 1;
	return x;
}
int idx;
int main()
{
	scanf("%d", &n);
	v[0] = 2e9;
	while(n --)
	{
		int t, x, y;
		scanf("%d%d", &t, &x);
		if(t == 1)
		{
			v[++ idx] = x;
			p[idx] = idx;
			dist[idx] = 1;
		}
		else if(t == 2)
		{
			scanf("%d", &y);
			x = find(x), y = find(y);
			if(x != y)
			{
				if(cmp(y, x)) swap(x, y);
				p[y] = x;
				merge(x, y);
			}
		}
		else if(t == 3)
		{
			printf("%d\n", v[find(x)]);
		}
		else 
		{
			x = find(x);
			if(cmp(r[x], l[x])) swap(l[x], r[x]);
			p[x] = l[x], p[l[x]] = l[x];
			merge(l[x], r[x]);
		}
	}
	return 0;
}