左偏树 学习笔记

左偏树是一种可并堆，具有堆的性质，同时支持快速合并。

定义和性质

对于一棵二叉树，定义一个节点的 $\mathrm{dist}$ 为这个点到它的子树中距离它最近的叶子的路径上的节点数。一个空节点的 $\mathrm{dist}$ 为 $0$，叶子节点的 $\mathrm{dist}$ 为 $1$，根的 $\mathrm{dist}$ 不超过 $\lceil\log (n+1)\rceil$。

左偏树是一棵二叉树，它不仅具有堆（本文为小根堆）的性质，并且是「左偏」的：每个节点左儿子的 $\mathrm{dist}$ 都大于等于右儿子的 $\mathrm{dist}$。因此，左偏树每个节点的 $\mathrm{dist}$ 都等于其右儿子的 $\mathrm{dist}$ 加一。

核心操作：合并

合并两个堆时，由于要满足堆性质，先取值较小的那个根作为合并后堆的根节点，然后将这个根的左儿子作为合并后堆的左儿子，递归地合并其右儿子与另一个堆，作为合并后的堆的右儿子。为了满足左偏性质，合并后若左儿子的 $\mathrm{dist}$ 小于右儿子的 $\mathrm{dist}$，就交换两个儿子，时间复杂度 $\mathcal O(\log n)$。

int merge(int x, int y) {
	if (!x || !y) return x | y;
	if (t[x].x > t[y].x) swap(x, y);
	t[t[x].r=merge(t[x].r,y)].f = x;
	if (t[t[x].r].d > t[t[x].l].d) swap(t[x].l, t[x].r);
	t[x].d = t[t[x].r].d + 1;
	return x;
}

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

由于并查集需要路径压缩才能保证时间复杂度，因此这题需要将删掉的点重新指向合并后的新根，因此有些细节要注意。

const int N = 1e5 + 7;
int n, m, f[N];
bool v[N];
struct T {
	int x, l, r, f, d;
} t[N];

int get(int x) {
	return x == f[x] ? x : (f[x] = get(f[x]));
}

int merge(int x, int y) {
	if (!x || !y) return x | y;
	if (t[x].x > t[y].x || (t[x].x == t[y].x && x > y)) swap(x, y);
	t[t[x].r=merge(t[x].r,y)].f = x;
	if (t[t[x].l].d < t[t[x].r].d) swap(t[x].l, t[x].r);
	t[x].d = t[t[x].r].d + 1;
	return f[y] = x;
}

int main() {
	rd(n), rd(m);
	for (int i = 1; i <= n; i++) rd(t[i].x), t[i].d = 1, f[i] = i;
	for (int i = 1, o, x, y; i <= m; i++) {
		rd(o), rd(x);
		if (o == 1) {
			rd(y);
			if (v[x] || v[y]) continue;
			x = get(x), y = get(y);
			if (x != y) merge(x, y);
		} else if (v[x]) print(-1);
		else {
			x = get(x), v[x] = 1, print(t[x].x);
			f[x] = f[t[x].l] = f[t[x].r] = merge(t[x].l, t[x].r);
		}
	}
	return 0;
}

参考资料

• OI Wiki 左偏树