左偏树问题

解题思路

本题需要维护一个小根堆的集合，其实就是维护一个左偏树。

需要实现四种操作，一是插入一个新堆，堆中只有一个数，就是建一个只有一个节点的左偏树。二是将某两个数所在的左偏树合并。三是输出某个数所在的左偏树的最小值，也就是根节点的权值。四是删除某个数所在的左偏树的最小值，也就是删除根节点。

而操作二只有在两个数不在同一棵左偏树中时才能合并，因此本题还需要维护一个并查集。用并查集去记录每个节点所在的左偏树的根节点。这样就能快速知道某两个点是否在同一棵左偏树中。如果不在同一棵左偏树中我们再去进行合并操作。

操作三其实就是找到某个数所在的根节点，可以直接在并查集中找到，然后查询一下权值即可。

操作四是将某个左偏树的根节点删掉，在左偏树中删掉在将左、右子树合并非常容易，但是对应的并查集中也要将这个根节点删掉，而并查集并不支持删除节点的操作。但是并查集支持换根操作，当前这个并查集的根节点被我们删去后，根节点会变成它的左、右子树的根节点之一，而这个节点也是在并查集中的，因此我们可以将当前这个并查集的根换成新的左偏树的根节点，操作也非常简单，原根节点在并查集中的父节点指向自己，我们只需要让它的父节点指向新的根节点，然后让新的根节点的父节点指向自己，这样当前集合的根节点就从原根节点变成了新根节点。然后此时原根节点虽然还在并查集的集合中，但是在左偏树中我们已经将这个点删去了，因此我们之后都不会再用到这个点，因此就算并查集中存在这个点，也不会影响我们后续的操作。

然后由于本题的所有操作都必须是 $O(logn)$ 的复杂度，因此并查集用路径压缩即可，不需要加按秩合并

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 200010;

int n;
//v[i] 表示节点 i 的权值
//dist[i] 表示距离节点 i 最近的空节点的距离
//l[i] 表示节点 i 的左儿子
//r[i] 表示节点 i 的右儿子
int v[N], dist[N], l[N], r[N], idx;
int p[N]; //并查集

bool cmp(int x, int y) //判断 x 的权值是否小于 y 的权值，如果权值相等则判断下标
{
    if(v[x] != v[y]) return v[x] < v[y];
    return x < y;
}

int find(int x) //返回 x 所在的集合
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int merge(int x, int y) //将 x 和 y 所在的左偏树合并，并返回合并后的根节点
{
    if(!x || !y) return x + y; //如果 x 或 y 是空节点，直接合成一棵
    if(cmp(y, x)) swap(x, y); //保证 x < y
    //合并后 x 是根节点，继续合并 x 右子树
    r[x] = merge(r[x], y);
    if(dist[l[x]] < dist[r[x]]) swap(l[x], r[x]); //保证 x 的左子树距离 > 右子树距离
    dist[x] = dist[r[x]] + 1; //x 的距离 = 右子树距离 + 1，右子树发生改变，x 的距离也需要更新
    return x; //返回合并后的根节点
}

int main()
{
    scanf("%d", &n);

    v[0] = 2e9; //将 0 节点的权值设为正无穷，用于处理边界情况
    while(n--)
    {
        int op, x, y;
        scanf("%d%d", &op, &x);
        if(op == 1) //插入一个新的左偏树，左偏树中只有一个值 x
        {
            v[++idx] = x; //建立左偏树
            dist[idx] = 1; //每个节点的距离最开始是 1
            p[idx] = idx; //建立并查集
        }
        else if(op == 2) //将 x 和 y 所在的左偏树合并
        {
             scanf("%d", &y);
             x = find(x), y = find(y);
             if(x != y) //不在同一个左偏树中，需要合并
             {
                 if(cmp(y, x)) swap(x, y); //保证 x < y
                 p[y] = x; //合并后根节点是 x
                 merge(x, y); //合并两个左偏树
             }
        }
        else if(op == 3) printf("%d\n", v[find(x)]); //输出 x 所在的左偏树的最小值
        else //删除 x 所在左偏树的最小值
        {
            x = find(x);
            if(cmp(r[x], l[x])) swap(r[x], l[x]); //保证 v[l[x]] < v[r[x]]
            //此时 l[x] 是左偏树的新根节点
            p[x] = l[x], p[l[x]] = l[x]; //将当前集合的根节点换成 l[x]
            merge(l[x], r[x]); //合并左、右子树
        }
    }
    return 0;
}