Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

左偏树

Posted on Edited on

不知道为什么没保存，只能鸽着了，下次再来补。

不鸽了，开补。

简介

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

支持的操作

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

满足的基本性质

  • 左偏树具有 堆性质 ，即若其满足小根堆的性质，则对于每个结点 $x$ ，有 $v_x≤v_{lc},v_x≤v_{rc}$。
  • 左偏树具有 左偏性质 ，即对于每个结点 $x$ ,有 $dist_{lc}\ge dist_{rc}$ 。

核心操作：合并操作

  • 其实需要的函数就这么一个。
  • 定义 $merge(x,y)$ 为合并两棵分别以 $x,y$ 为根节点的左偏树，其返回值为合并之后的根节点。
  • 首先不考虑左偏性质，我们描述一下合并两个具有堆性质的树的过程。假设我们要合并的是小根堆。
  • 1.若$v_x \le v_y$ 则将 $x$ 作为根节点，否则交换 $x,y$。
  • 2.向下递归使 $y$ 与 $x$ 的右儿子合并，并返回新儿子节点的编号。
  • 3.当 $x$ 或 $y$ 之中有空节点时，返回 $x + y$（避免分类讨论）。
1
2
3
4
5
6
7
8
9
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. 左偏树

  • $luogu$ 的例题太 $large$ 了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#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;
}