[算法]左偏树

wangyibo201026 · 2022-07-31 09:20:26 · 个人记录

什么是左偏树

左偏树是可并堆的一种，可以支持查询某个堆的最小值，合并两个堆。

左偏树思想

首先一些专有名词：

• 外节点：任意儿子是空的节点。

• 距离：节点 x 的距离 dist_x 定义为在 x 的子树中里 x 最近的外节点的距离。

左偏树到底怎么左偏，首先看一下左偏思想：

对于每个节点 x，总有 dist_l \ge dist_r。

结合我们的堆（小根堆）思想：

对于每个节点 x，总有 val_x \le val_l, val_x \le val_r。

一些结论需要记住：

• 对于任意节点 x，都有 dis_x = dist_r + 1。

• 左偏树的根节点距离是 O(\log n) 的。

我们显然可以发现，如果合并一个普通堆，时间复杂度是 O(h) 的，很差。

这里合并操作作者不想讲，去看左偏树题解。

代码

代码：

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e5 + 5;

int n, m;
int a[N];

int ls[N], rs[N], dist[N], fa[N];
bool vis[N];

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

int merge(int x, int y){
    if(!x || !y){
        return x + y; 
    }
    if(a[y] < a[x]){
        swap(x, y);
    }
    rs[x] = merge(rs[x], y);
    if(dist[ls[x]] < dist[rs[x]]){
        swap(ls[x], rs[x]);
    }
    dist[x] = dist[rs[x]] + 1;
    return x;
}

signed main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        fa[i] = i;
    }
    dist[0] = -1;
    while(m--){
        int op;
        cin >> op;
        if(op == 1){
            int x, y;
            cin >> x >> y;
            if(!vis[x] && !vis[y]){
                x = find(x);
                y = find(y);
                if(x != y){
                    fa[x] = fa[y] = merge(x, y);
                }
            }
        }
        else if(op == 2){
            int x;
            cin >> x;
            if(vis[x]){
                cout << -1 << endl;
                continue;
            }
            x = find(x);
            cout << a[find(x)] << endl;
            vis[x] = true;
            fa[ls[x]] = fa[rs[x]] = fa[x] = merge(ls[x], rs[x]);
            ls[x] = rs[x] = dist[x] = 0;
        }
    }
    return 0;
}