「学习笔记」重修左偏树

左偏树，是一种可并堆，同时也是一棵二叉树，可以快速地完成合并操作。

dist 的性质

对于一棵二叉树，我们定义左孩子或右孩子为空的节点为外节点，定义外节点的 (text{dist}) 为 (1)，空节点的 (text{dist}) 为 (0)，不是外节点也不是空节点的 (text{dist}) 为其到子树中最近的外节点的距离加一。
一棵根的 (text{dist}) 为 (x) 的二叉树至少有 (2^x – 1) 个节点。此性质所有二叉树都有，并非左偏树特有。
(text{dist}) 不是深度，左偏树的深度没有保证，一条向左的链也是左偏树。

左偏树的性质

左偏树是一棵二叉树，并且是“左偏”的，即每个节点左儿子的 (text{dist}) 都大于等于右儿子的 (text{dist})。
因此，左偏树中每个节点的 (text{dist}) 是它右儿子的 (text{dist}) 加一。

变量

int lson[N], rson[N], fa[N], fat[N];
ll val[N], dist[N];

lson: 左孩子（左偏）；
rson: 右孩子；
fa: 父节点；
fat: 祖先（并查集）；
val: 权值；
dist: 就是 (text{dist})。

操作

• 合并

int merge(int x, int y) { // 合并
	if (!x || !y) {
		return x | y;
	}
	if (val[x] > val[y] || (val[x] == val[y] && x > y))
		swap(x, y);
	rson[x] = merge(rson[x], y);
	fat[rson[x]] = fa[rson[x]] = x;
	if (dist[lson[x]] 

if (!x || !y) { return x | y; } 如果与空节点合并，则直接合并即可
if (val[x] > val[y] || (val[x] == val[y] && x > y)) 说明这是个小根堆，小元素在上面。
if (dist[lson[x]] 维护左偏的性质。

• 删除任意一个节点

左偏树是不支持删除给定权值的点的，只能删除知道点的标号的点。

void earse(int u) { // 删除任意一点
	int tmp = merge(lson[u], rson[u]), fu = fa[u];
	fat[tmp] = fa[tmp] = fu;
	fat[u] = fa[u] = tmp;
	lson[fu] == u ? lson[fu] = tmp : rson[fu] = tmp;
	while (fu) {
		if (dist[lson[fu]] 

int tmp = merge(lson[u], rson[u]), fu = fa[u]; 先将被删节点的左右孩子合并。
fat[tmp] = fa[tmp] = fu; 处理好父亲和孩子的关系。

while (fu) {
	if (dist[lson[fu]] 

删除点之后可能不符合左偏性质，需要我们向上修改，直到到根节点或符合左偏性质为止。

• 查询 (u) 点所在堆的堆顶元素的标号

这个操作类似于并查集操作。

int find(int u) { // 查询堆顶的元素的标号
	return (fat[u] == u || fat[u] == 0) ? u : fat[u] = find(fat[u]);
}

• 删除 (u) 点所在堆的堆顶元素

void pop(int u) { // 弹出 u 点所在对的堆顶元素
	int g = find(u);
	earse(g);
}

• 查询 (u) 点所在堆的堆顶元素

ll top(int u) { // 查询 u 点所在堆的堆顶元素
	int g = find(u);
	return val[g];
}

• 建树操作

int build(int n) { // 建树
	queue q;
	for (int i = 1; i  1) {
		x = q.front(), q.pop();
		y = q.front(), q.pop();
		z = merge(x, y), q.push(z);
	}
	return q.front();
}

模板

// 左偏树（小根堆）
struct leftist_tree {
	int lson[N], rson[N], fa[N], fat[N];
	ll val[N], dist[N];

	int merge(int x, int y) { // 合并
		if (!x || !y) {
			return x | y;
		}
		if (val[x] > val[y] || (val[x] == val[y] && x > y))
			swap(x, y);
		rson[x] = merge(rson[x], y);
		fat[rson[x]] = fa[rson[x]] = x;
		if (dist[lson[x]]  q;
		for (int i = 1; i  1) {
			x = q.front(), q.pop();
			y = q.front(), q.pop();
			z = merge(x, y), q.push(z);
		}
		return q.front();
	}
};

pb_ds 中的堆

__gnu_pbds :: priority_queue

成员函数

push(): 向堆中压入一个元素，返回该元素位置的迭代器。
pop(): 将堆顶元素弹出。
top(): 返回堆顶元素。
size(): 返回元素个数。
empty(): 返回是否非空。
modify(point_iterator, const key): 把迭代器位置的 key 修改为传入的 key，并对底层储存结构进行排序。
erase(point_iterator): 把迭代器位置的键值从堆中擦除。
join(__gnu_pbds :: priority_queue &other): 把 other 合并到 *this 并把 other 清空。

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net