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

定义及性质

对于一棵二叉树，定义外节点为左儿子或右耳子为空的节点，定义其的 (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。

(1le nle 10^5)。

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

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

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

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

#include 
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 > 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 

机房租用，北京机房托管，大带宽租用，IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net