左偏树属于可并堆的一种，可并堆，也就是可以在较低的时间复杂度下完成对两个堆的合并。

定义及性质

对于一棵二叉树，定义外节点为左儿子或右耳子为空的节点，定义其的 \(dist\) 为 \(1\)，而不是外节点的 \(dist\) 为其到子树中最近的外节点距离 \(+1\)。空节点的 \(dist\) 为 \(0\)。 例如，对于这一棵二叉树，其的外节点和 \(dist\) 如下：

定义：有一棵二叉树，如果它不仅满足堆的性质，对其的每一个节点都有左儿子的 \(dist\) 大于等于右儿子的 \(dist\)，则称其为“左偏树”。为什么会“左偏”呢？不妨举几个例子：

其中，前两个为左偏树，可以发现，它们确实是向左偏的；而后两棵树不是左偏树，因为标红的节点其左儿子的 \(dist\) 小于右儿子，值得注意的是，第四幅图根节点没有左儿子，根据定义，空节点的 \(dist\) 为 \(0\)，比右儿子的 \(1\) 小，所以其为左偏树。

性质：

• 对于任意一个非外节点，\(dist_u=dist_{rson}+1\)。根据 \(dist\) 的定义，\(dist_u\) 要么为左儿子 \(dist\) 加一，要么为右儿子 \(dist\) 加一，由于要求是“最近”的外节点，加上左偏树的性质，\(dist_u=dist_{rson}+1\)。

• 一课左偏树的 \(dist\) 最大值在 \(\log n\) 级别。假设根的 \(dist\) 为 \(x\)，则这棵二叉树至少前 \(x-1\) 层为“满的”，那么就至少有 \(2^x-1\) 个节点，注意到，这一点对任何一棵二叉树都适用。还有重要的是左偏树的深度没有任何保证，一条向左偏的链仍然是左偏树，只有其的 \(dist\) 最大值有保证。

合并操作

左偏树的核心是合并操作。下文以小根堆为例。

首先，为了满足堆性质，应取两个堆中根较小的那个根作为新的根，作为根的堆左儿子不动，把右儿子和另一个堆合并，一直递归下去，而为了满足左偏树的性质，如果左儿子的 \(dist\) 比右儿子小了，应交换其左右儿子（实际上，还有一种不用交换的方法，就是把 \(dist\) 小的那个儿子之间当做右儿子）。

以下是一个例子（节点中的数为值，红色的数为 \(dist\)）：

时间复杂度：由于每递归一层，其中一个堆的根的 \(dist\) 就会减 \(1\)，根据 \(dist\) 的最大值在 \(\log\) 级别的性质，合并的时间复杂度为 \(O(\log x+\log y)\)（其中 \(x,y\) 为两个堆的大小）。

int merge(int x, int y) {
		if (!x || !y) return x | y;
		//如果其中有一个堆为空的话就返回另一个堆
		if (t[x].v > t[y].v) swap(x, y);//选根较小的堆
		t[x].rs = merge(t[x].rs, y);//合并右儿子
		if (t[t[x].rs].dist > t[t[x].ls].dist) swap(t[x].rs, t[x].ls);
		//使其保持左偏堆的性质
		t[x].dist = t[t[x].rs].dist + 1;//更新 dist
		return x;
	}

其它操作

插入元素：直接把这一个节点当成一个堆，合并即可。

删除根：合并根的左右儿子。

删除任意节点：将左右儿子合并并从下往上更新 \(dist\) 并通过交换左右儿子维护左偏树的性质，\(dist\) 不更新时结束递归，时间复杂度 \(O(\log n)\)。

整个堆加或乘一个数：在根上打上标记，合并时下传即可。

具体实现

P3377 【模板】左偏树（可并堆）

一开始有 \(n\) 个小根堆，你需要支持以下两个操作：

• 合并 \(x\) 和 \(y\) 所在的堆，若 \(x\) 或 \(y\) 已经在同一个堆中或已被删去则忽略；
• 查询第 \(x\) 个堆的堆顶并弹出，若 \(x\) 被删去则输出 -1。

\(1\le n\le 10^5\)。

分析：其实两个操作在之前都讲过了，不过注意对于查询堆顶或判断是否在同一个堆中，警惕以下错误的写法：

int Get(int x) { 
	while(S[x].F) x = S[x].F; 
	return x;
}

这相当于暴力跳父亲。之前说过，左偏树的深度是没有保障的，这样的方法有可能被卡到 \(O(n)\)。正确的做法是使用并查集+路径压缩维护，复杂度近似于 \(O(\log n)\)。

然后还有一个常会犯的错误是当弹出堆顶时，（并查集维护）堆顶的祖先应更改为合并后的根节点。虽然这个点以后不会用到了，但是之前把它当做祖先的点仍会访问到它（因为使用了路径压缩），于是就会导致找到错误的根节点。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
namespace Leftist_tree {
	int fa[N];
	bool vis[N];
	struct node {
		int v;
		int ls, rs;
		int dist;
	}t[N];
	int find(int x) {
		if (fa[x] == x) return x;
		return fa[x] = find(fa[x]);
	}
	int merge(int x, int y) {
		if (!x || !y) return x | y;
		if (t[x].v > t[y].v) swap(x, y);
		t[x].rs = merge(t[x].rs, y);
		if (t[t[x].rs].dist > t[t[x].ls].dist) swap(t[x].rs, t[x].ls);
		t[x].dist = t[t[x].rs].dist + 1;
		return x;
	}
}
using namespace Leftist_tree;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), std::cout.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> t[i].v, fa[i] = i;
	while (m--) {
		int op, x, y;
		cin >> op >> x;
		if (op == 1) {
			cin >> y;
			if (vis[x] || vis[y] || find(x) == find(y)) continue;
			fa[find(x)] = fa[find(y)] = merge(find(x), find(y));
		}
		else {
			if (vis[x]) cout << "-1\n";
			else {
				x = find(x), vis[x] = true, cout << t[x].v << "\n"; 
				fa[x] = fa[t[x].ls] = fa[t[x].rs] = merge(t[x].ls, t[x].rs);
			}
		}
	} 
	return 0;
}

热门相关：有个人爱你很久   富贵不能吟   锦庭娇   神算大小姐   买妻种田：山野夫君，强势宠！