【笔记】左偏树

2023-12-21 18:03:47


算法进阶课整理

CSDN个人主页:更好的阅读体验

Start

左偏树功能简介

左偏树本质上是一个二叉堆,支持 O ( 1 ) O(1) O(1) 求最值, O ( log ? n ) O(\log n) O(logn) 删除最值。

不过由于它还支持 O ( log ? n ) O(\log n) O(logn) 合并两个二叉堆,所以一般左偏树相关的题目都是若干棵左偏树构成森林。

定义与一些性质

左偏树中每个节点维护两个值,点权 v v v 和与最近空节点的距离 d i s t dist dist

点权 v v v 满足堆性质,即当前点点权小于任意一个儿子的点权。这种二叉堆我们一般称为“小根堆”。同样的,大根堆中当前点点权大于任意一个儿子的点权。为了方便,本篇文章主要探究小根堆的性质。

与最近空节点的距离 d i s t dist dist 满足:

  1. 叶子节点的 d i s t = 1 dist=1 dist=1
  2. 每个节点左儿子的 d i s t dist dist 都大于等于右儿子的 d i s t dist dist。这就会导致整棵树是一个向左偏的形状,因此被称为左偏树。

因此,每个节点的 d i s t dist dist 都是右儿子的 d i s t + 1 dist+1 dist+1

下图就是一棵左偏树。

zps
一棵有 n n n 个节点的左偏树,根的 d i s t ≤ log ? 2 ( n + 1 ) dist \leq \log_2 (n+1) distlog2?(n+1),因为一棵根的 d i s t dist dist x x x 的二叉树至少有 x ? 1 x-1 x?1 层是满二叉树,那么就至少有 2 x ? 1 2^x-1 2x?1 个节点。

由于左偏树的时间复杂度与 d i s t dist dist 正相关,所以左偏树操作的复杂度也为 O ( log ? n ) O(\log n) O(logn)


核心操作:合并

算法流程
  1. 比较两棵左偏树 x , y x,y x,y 根节点点权的大小。不妨设 v root? x ≤ v root? y v_{\text{root}\ x}\leq v_{\text{root}\ y} vroot?x?vroot?y?(如果不满足的话交换 x , y x,y x,y 即可)。
  2. 易证 ? u ∈ y , v u ≥ v root? x \forall u \in y,v_u\geq v_{\text{root}\ x} ?uy,vu?vroot?x?。因此将 root? x \text{root}\ x root?x 作为合并后的左偏树的根节点是合法的。
  3. 由于堆没有限制左右儿子点权的关系,所以 x x x 左子树也不需要改变, y y y 直接递归地合并到 x x x 的右子树即可。
  4. 合并结束后,右子树的 d i s t dist dist 会改变,因此如果此时不满足左偏树性质,交换当前节点的左右儿子即可。
时间复杂度

由于每次合并会向下跳一级,所以最多跳 d i s t x + d i s t y dist_x+dist_y distx?+disty? 次就会跳到空节点。

d i s t x , d i s t y ≤ log ? 2 n dist_x,dist_y\leq \log_2n distx?,disty?log2?n,因此合并的时间复杂度为 O ( log ? n ) O(\log n) O(logn)

代码
int merge(int x, int y)
{
    if (!x || !y) return x + y; // 如果左右子树有一个为空就返回那个非空的
    if (cmp(y, x)) swap(x, y); // 保证dist较大的在左边
    tr[x].r = merge(tr[x].r, y); // 递归,将dist较小的向左合并
    if (tr[tr[x].l].dist < tr[tr[x].r].dist) swap(tr[x].l, tr[x].r);
    // 如果合并之后不满足左偏性质就交换左右子树
    tr[x].dist = tr[tr[x].r].dist + 1;
    // 更新当前节点dist为右子树dist+1
    return x; // 返回合并之后根节点编号
}

其他的操作

插入
算法流程

插入操作没有专门的做法,我们考虑新建一个仅含有要插入节点的左偏树,将其合并到想要合并的树中即可。

时间复杂度 O ( log ? n ) O(\log n) O(logn)
找最值
算法流程

输出相应左偏树顶的点权即可。

时间复杂度 O ( 1 ) O(1) O(1)
删除最值
算法流程

由于最值为这个左偏树根节点的点权,因此删去这个点之后根节点就被删掉了。此时考虑合并根节点的左右子树即可。

时间复杂度 O ( log ? n ) O(\log n) O(logn)

例题 1 1 1:AcWing 2714. 左偏树

原题链接
题目描述

你需要维护一个小根堆的集合,初始时集合是空的。

该集合需要支持如下四种操作:

  1. 1 a,在集合中插入一个新堆,堆中只包含一个数 a a a
  2. 2 x y,将第 x x x 个插入的数和第 y y y 个插入的数所在的小根堆合并。数据保证两个数均未被删除。若两数已在同一堆中,则忽略此操作。
  3. 3 x,输出第 x x x 个插入的数所在小根堆的最小值。数据保证该数未被删除。
  4. 4 x,删除第 x x x 个插入的数所在小根堆的最小值(若最小值不唯一,则优先删除先插入的数)。数据保证该数未被删除。
输入格式

第一行包含整数 n n n,表示总操作数量。

接下来 n n n 行,每行包含一个操作命令,形式如题所述。

输出格式

对于每个操作 3 3 3,输出一个整数,占一行,表示答案。

数据范围

1 ≤ n ≤ 2 × 1 0 5 1 \le n \le 2 \times 10^5 1n2×105,
1 ≤ a ≤ 1 0 9 1 \le a \le 10^9 1a109,
1 ≤ x , y ≤ 1 \le x,y \le 1x,y 当前插入数的个数。
数据保证所有操作合法。

思路

发现题目输入的是第 x x x 个加入的数,并且还需要维护连通性,因此考虑并查集。

使用并查集维护连通块,连通块的根节点就是对应的左偏树的根节点。这样能快速地找到每个节点对应的根节点编号。

  • 操作 1 1 1:按加入的顺序分配编号即可。
  • 操作 2 2 2:如果两个点不在同一个连通块内,就合并两个左偏树,同时合并两个连通块。
  • 操作 3 3 3:直接输出根节点值即可。
  • 操作 4 4 4:左偏树的删除操作较好实现,不过并查集一般难以实现删除操作,于是考虑换根。由于我们删除的肯定是根节点,而根节点的父亲指针指向自身,所以考虑将根节点父指针指向合并后的新根。同时,新根的父指针指向自己。这样就维护了新根节点的信息。至于还在连通块中的那个应该被删除的节点,反正遍历不到,就不用管了。

代码
#include <iostream>

using namespace std;

const int N = 200010;

struct Leftist_Tree_Node
{ // 定义左偏树节点
    int l, r; // 左右儿子
    int v, dist; // 点权、距离
    void init(int _v)
    {
        v = _v, dist = 1;
    }
}tr[N];

int n, idx; // idx时间戳,记录插入点的顺序
int p[N]; // 并查集父指针

int find(int x) // 并查集
{
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}

inline bool cmp(int x, int y) // 比较两个点点权,如果x的点权较小就返回1,否则返回0
{
    if (tr[x].v != tr[y].v) return tr[x].v < tr[y].v;
    return x < y; // 题目要求先删早加入的点
}

int merge(int x, int y) // 合并
{
    if (!x || !y) return x + y;
    if (cmp(y, x)) swap(x, y);
    tr[x].r = merge(tr[x].r, y);
    if (tr[tr[x].l].dist < tr[tr[x].r].dist) swap(tr[x].l, tr[x].r);
    tr[x].dist = tr[tr[x].r].dist + 1;
    return x;
}

int main()
{
    int op, x, y;
    scanf("%d", &n);
    tr[0].init(1e9); // 处理边界情况
    while (n -- )
    {
        scanf("%d%d", &op, &x);
        if (op == 1)
        {
            tr[ ++ idx].init(x); // 新建节点,分配编号
            p[idx] = idx; // 初始化并查集
        }
        else if (op == 2)
        {
            scanf("%d", &y);
            int r1 = find(x), r2 = find(y); // 找到两个根节点
            if (r1 != r2) // 如果不在一个连通块内
            {
                if (cmp(r2, r1)) swap(r1, r2); // 比大小,将点权小的放前面
                merge(r1, r2); // 左偏树合并
                p[r2] = r1; // 连通块合并
            }
        }
        else if (op == 3) printf("%d\n", tr[find(x)].v); // x所在连通块根节点的权值
        else
        {
            int rt = find(x);
            if (cmp(tr[rt].r, tr[rt].l)) swap(tr[rt].l, tr[rt].r); // 交换
            merge(tr[rt].l, tr[rt].r); // 合并左右子树,即删除根节点
            p[rt] = tr[rt].l, p[tr[rt].l] = tr[rt].l; // 并查集换根
        }
    }

    return 0;
}

例题 2 2 2:洛谷 P3377 【模板】左偏树/可并堆

原题链接
题目描述

如题,一开始有 n n n 个小根堆,每个堆包含且仅包含一个数。接下来需要支持两种操作:

  1. 1 x y:将第 x x x 个数和第 y y y 个数所在的小根堆合并(若第 x x x 或第 y y y 个数已经被删除或第 x x x 和第 y y y 个数在用一个堆内,则无视此操作)。

  2. 2 x:输出第 x x x 个数所在的堆最小数,并将这个最小数删除(若有多个最小数,优先删除先输入的;若第 x x x 个数已经被删除,则输出 ? 1 -1 ?1 并无视删除操作)。

输入格式

第一行包含两个正整数 n , m n, m n,m,分别表示一开始小根堆的个数和接下来操作的个数。

第二行包含 n n n 个正整数,其中第 i i i 个正整数表示第 i i i 个小根堆初始时包含且仅包含的数。

接下来 m m m 行每行 2 2 2 个或 3 3 3 个正整数,表示一条操作,格式如下:

操作 1 1 11 x y

操作 2 2 22 x

输出格式

输出包含若干行整数,分别依次对应每一个操作 2 2 2 所得的结果。

数据范围

对于 30 % 30\% 30% 的数据: n ≤ 10 n\le 10 n10 m ≤ 10 m\le 10 m10
对于 70 % 70\% 70% 的数据: n ≤ 1 0 3 n\le 10^3 n103 m ≤ 1 0 3 m\le 10^3 m103
对于 100 % 100\% 100% 的数据: n ≤ 1 0 5 n\le 10^5 n105 m ≤ 1 0 5 m\le 10^5 m105,初始时小根堆中的所有数都在 int 范围内。


思路

本题与上题大致相同,但需要手动判断一个数是否已经被删除。由于并查集不能删除元素,所以考虑为每个节点维护一个标记表示是否被删除。

注意读题。

这个最小数 删除(若有多个最小数,优先删除先输入的;若 x x x 个数 已经被删除,则输出 ? 1 -1 ?1 并无视删除操作)。

具体细节见代码。

代码
#include <iostream>

using namespace std;

const int N = 100010;

struct Leftist_Tree_Node
{
	int l, r;
	int v, dist;
	void init(int _v)
	{
		v = _v, dist = 1;
	}
}tr[N];

int n, m;
int p[N];
bool st[N]; // 如果已经被删除,则为 true

int find(int x)
{
	if (x != p[x]) p[x] = find(p[x]);
	return p[x];
}

inline bool cmp(int x, int y)
{
	if (tr[x].v != tr[y].v) return tr[x].v < tr[y].v;
	return x < y;
}

int merge(int x, int y)
{
	if (!x || !y) return x + y;
	if (cmp(y, x)) swap(x, y);
	tr[x].r = merge(tr[x].r, y);
	if (tr[tr[x].l].dist < tr[tr[x].r].dist) swap(tr[x].l, tr[x].r);
	tr[x].dist = tr[tr[x].r].dist + 1;
	return x;
}

int main()
{
	int op, x, y;
	tr[0].init(2e9);
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i ++ )
	{
		scanf("%d", &x);
		tr[i].init(x), p[i] = i;
	}

	while (m -- )
	{
		scanf("%d%d", &op, &x);
		if (op == 1)
		{
			scanf("%d", &y);
			int r1 = find(x), r2 = find(y);
			if (st[x] || st[y] || r1 == r2) continue;
			// 注意 st 里是原数据而不是并查集根节点
			if (cmp(r2, r1)) swap(r1, r2);
			p[r2] = r1;
			merge(r1, r2);
		}
		else
		{
			int rt = find(x);
			if (st[x]) puts("-1");
			// 注意读题。当前点已经被删除输出-1.
			else
			{
				printf("%d\n", tr[rt].v);
				if (cmp(tr[rt].r, tr[rt].l)) swap(tr[rt].l, tr[rt].r);
				merge(tr[rt].l, tr[rt].r);
				st[rt] = true; // 注意读题。删除最小数,即删除根节点。
				p[rt] = tr[rt].l, p[tr[rt].l] = tr[rt].l;
			}
		}
	}
	return 0;
}

End

最后,如果觉得对您有帮助的话,点个赞再走吧!

文章来源:https://blog.csdn.net/xingchen_2008/article/details/135131816
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。