【学习笔记】左偏树

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

定义及性质

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

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