可并堆——左偏树实现

可并堆——左偏树实现

可并堆

堆是优先队列的一种实现方式，堆中父节点大于等于（或小于等于）两子节点，每次的删除，查询，插入都是 $O(log_2n)$ 的复杂度

• 我们考虑两个堆的合并问题，如果让小的堆合并到大的堆，一个一个插入，时间复杂度 $O(nlog_2n)$ 效率往往不能满足要求。我们需要一个合并复杂度大致为 $O(log_2(m + n))$ 的可并堆

左偏树

• 左偏树可以用来实现这样的可并堆，首先我们可以定义一个节点的dis值为这个节点的右节点的dis值+1，直观地来说，一个节点的dis值就是从这个节点开始一直往右儿子走，最多能走多远
  
  
• 然后对左偏树可以这样理解：
  • 一棵左偏树首先是个堆
  • 对左偏树上所有节点，都有

  左儿子的dis值大于等于右儿子的dis值

- 定义结束，我们可能要问如何建一棵左偏树？这里我要说，左偏树和传统的堆不同，没有pushup操作，左偏树唯一的操作就是合并merge。 >也就是说，我们建立左偏树，是将每个节点都看成一棵左偏树，然后一步一步合并起来的，所以我们要先明确什么是合并操作。

合并操作

对左偏树最核心的合并操作，是这样的(假设数越小优先级越大)：

• 1.对以x，y为根节点的两棵左偏树合并，首先若x为空则合并结果为y，若y为空则合并结果为x（显然）。
  
  
• 2.若都不为空，则检查x，y节点的值，让值大的节点与值小的节点的右儿子合并，这一步是为了维持堆的性质，保证父亲小于子节点（以下假设x节点值更小）
  
  
• 3.合并之后，检查x的左右儿子节点的dis值，如果左儿子的dis小于右儿子的dis，则交换左右儿子节点，这一步是为了维持左偏性质。
  
  
• 4.将x节点的dis设为右儿子节点的dis+1

如此递归操作即可在 $O(log_2(m + n))$ 内完成两个左偏树的合并

其他操作

其他操作建立在合并之上，下面是常见的几种。

• 插入节点

  将待插入的节点作为一棵左偏树与树根合并即可

• 删除

  对于堆来说，删除只能作用于根节点。所以把根节点与左右儿子断开，然后合并左右子树即可

• 建树

  对一个序列建左偏树的较理想方式，是使用队列，每次出队两棵树（单节点也是左偏树），将两棵树合并然后放在队尾，直到队内只剩下一棵左偏树

其他事项

• 这里可能有疑问，左偏树深度怎么保证？

• 事实上由定义，左偏树是可以变成一条链的，这看上去对于堆的影响很小，但是这使得：

  • 1.左偏树不能用二进制运算的数组实现
  • 2.寻找一个节点在左偏树上的根，可能退化到 $O(n)$ 复杂度(模板题中有涉及)

模板题 洛谷P3377

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
struct ab
{
	int v;
	int dis;
	int ls;
	int rs;
	int fa;
} aa[200005];

void sw(int& a, int& b)
{
	int t = a;
	a = b;
	b = t;
}

bool bk[100005] = {0};

int merge(int x, int y)
{
	if (!x)
	{
		return y;
	}
	if (!y)
	{
		return x;
	}
	if (aa[x].v > aa[y].v || (aa[x].v == aa[y].v && x > y))
	{
		sw(x, y);
	}
	aa[x].rs = merge(aa[x].rs, y);
	aa[aa[x].rs].fa = x;
	if (aa[x].ls)
	{
		aa[aa[x].ls].fa = x;
	}
	if (aa[aa[x].ls].dis < aa[aa[x].rs].dis)
	{
		sw(aa[x].ls, aa[x].rs);
	}
	if (!aa[x].rs)
	{
		aa[x].dis = 0;
	}
	else
	{
		aa[x].dis = aa[aa[x].rs].dis + 1;
	}
	return x;
}

int mn(int x)
{
	if (aa[x].fa != x)
	{
		aa[x].fa = mn(aa[x].fa);
	}
	return aa[x].fa;
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i)
	{
		scanf("%d", &aa[i].v);
		aa[i].fa = i;
	}
	for (int i = 1; i <= m; ++i)
	{
		int sele;
		scanf("%d", &sele);
		if (sele == 1)
		{
			int xx, yy;
			scanf("%d%d", &xx, &yy);
			int mnx = mn(xx);
			int mny = mn(yy);
			if (bk[xx] || bk[yy] || mnx == mny)
			{
				continue;
			}
			
			merge(mn(xx), mn(yy));
		}
		else
		{
			int xx;
			scanf("%d", &xx);
			if (!bk[xx])
			{
				int id = mn(xx);
				printf("%d\n", aa[id].v);
				aa[aa[id].ls].fa = aa[id].ls;
				aa[aa[id].rs].fa = aa[id].rs;
				aa[id].v = 0;
				aa[id].fa = merge(aa[id].ls, aa[id].rs);
				bk[id] = true;
				aa[id].ls = 0;
				aa[id].rs = 0;
			}
			else
			{
				printf("-1\n");
			}
		}
	}
	return 0;
}

总之，没有完美的数据结构。但左偏树确实好写，不想用堆了（直接用平板电视更容易）

本文地址：https://blog.csdn.net/intmeX/article/details/107345140