AcWing 2714. 左偏树 题解

题目分析

本题要求维护一个小根堆的集合，初始为空，支持四种操作：插入新堆（堆中只有一个数）、合并两个数所在的小根堆、输出某个数所在小根堆的最小值、删除某个数所在小根堆的最小值。

解题思路

本题使用左偏树这种数据结构来实现小根堆集合的维护。左偏树是一种可并堆，它满足堆的性质（小根堆即父节点值小于等于子节点值），同时具有左偏性质（节点的左子树的距离大于等于右子树的距离，距离表示节点到最近叶子节点的边数）。通过并查集辅助判断元素是否在同一堆中，利用左偏树的合并操作来实现各种功能。

代码逐段分析

1. 头文件和全局变量定义

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

using namespace std;

const int N = 200010;

int n;
int v[N], dist[N], l[N], r[N], idx;
int p[N];

• 引入必要的头文件，iostream用于输入输出，cstring用于字符串操作，algorithm用于算法相关功能。
• 定义常量(N)，表示最大节点数。
• 变量(n)表示操作数量。
• v[N]存储每个节点的值；dist[N]存储每个节点的距离；l[N]和r[N]分别存储每个节点的左子节点和右子节点编号；idx用于给新插入的节点编号。

• p[N]是并查集数组，用于存储每个节点在并查集中的父节点。

• 比较函数

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

比较函数，用于比较两个节点。优先比较节点的值，值小的节点更优；若值相等，则比较节点编号，编号小的更优。

1. 并查集查找函数

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

并查集的查找函数，用于查找节点(x)所在集合的根节点，同时进行路径压缩，使后续查找更高效。

1. 左偏树合并函数

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;
}

左偏树的合并函数，用于合并两个左偏树(x)和(y)：
- 如果(x)或(y)为空，直接返回非空的那个树，若都为空则返回(0)。
- 确保(x)的根节点值小于等于(y)的根节点值，若不满足则交换(x)和(y)。
- 将(y)合并到(x)的右子树中。
- 检查并维护左偏性质，若右子树距离大于左子树距离，则交换左右子树。
- 更新(x)的距离为其右子树距离加(1)。
- 返回合并后的左偏树的根节点。

1. 主函数

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;
            dist[idx] = 1;
            p[idx] = idx;
        }
        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;
}

• 读取操作数量(n)，并设置一个哨兵节点(0)，其值为一个较大的数(2e9)，避免在合并等操作中出现问题。
• 循环处理每个操作：
  • 操作(1)：插入新堆，给新节点编号，设置节点值、距离，并在并查集中初始化该节点为独立的集合。
  • 操作(2)：合并两个数所在的堆，先通过并查集查找两个数所在堆的根节点，若不在同一堆中，则将一个堆的根节点作为另一个堆根节点的子节点，并调用合并函数合并两个左偏树。
  • 操作(3)：输出某个数所在堆的最小值，通过并查集找到该数所在堆的根节点，输出根节点的值。
  • 操作(4)：删除某个数所在堆的最小值，先找到该数所在堆的根节点，将根节点的左子树作为新的根节点，并在并查集中更新，最后合并根节点的左右子树。

时间复杂度分析

• 插入操作时间复杂度为(O(1))。
• 合并操作时间复杂度为(O(log n))，其中(n)是左偏树的节点数。
• 输出最小值操作时间复杂度为(O(1))（通过并查集找到根节点直接输出）。
• 删除最小值操作时间复杂度为(O(log n))，包括查找根节点、调整结构和合并子树等操作。
• 总体时间复杂度为(O(n log n))，其中(n)是操作的总数量。

空间复杂度分析

主要空间消耗在于存储左偏树的各种信息（节点值、距离、子节点编号）和并查集数组，空间复杂度为(O(N))，其中(N)是最大节点数。