To boldly go where no one has gone before.

【学习笔记】左偏树 / 可并堆

2019-10-04 22:17:26


模板 P3377

原理

定义: 若一个节点有儿子是空的,那么这个节点就叫空节点。而一个节点的$dis$值代表从这个节点出发,只经过右儿子到达一个空节点最少需要走的边数。

左偏树 的意思是:对于一棵树上的每一个节点,其左儿子的$dis$值大于等于右儿子的$dis$值,所以这棵树“向左偏”。

若以$u,v$为根的两个堆需要合并,由于已经维护好了左偏性质,所以只需要将$v$合并到$u$最右边的空节点,然后再递归维护左偏性质即可。

很显然,在最坏情况下,由于堆的性质,$dis[1]$到达$logn$,合并操作依然能够维持在$O(logn)$,是非常优秀的。


代码:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int n, m, heap[MAXN];
int fa[MAXN], ls[MAXN], rs[MAXN], dis[MAXN];
bool del[MAXN];

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

int Merge(int u, int v) {
    if (!u || !v)
        return u + v;
    if (heap[u] == heap[v] ? u > v : heap[u] > heap[v])
        swap(u, v); // 题目描述提到:优先删除原序列中靠前的
    rs[u] = Merge(rs[u], v); // 向右子树递归
    if (dis[ls[u]] < dis[rs[u]])
        swap(ls[u], rs[u]); // 维护左偏性质
    fa[ls[u]] = fa[rs[u]] = fa[u] = u; // 更新父亲
    dis[u] = dis[rs[u]] + 1; // 递归计算 dis 值
    return u;
}

void pop(int u) {
    del[u] = true;
    fa[ls[u]] = ls[u];
    fa[rs[u]] = rs[u];
    // 先把左右儿子拆出去
    fa[u] = Merge(ls[u], rs[u]);
    // 然后合并为一个新堆
}

void init() {
    for (int i = 1; i <= n; i++)
        fa[i] = i;
}

int main() {
    dis[0] = -1;
    // 注意!此处是为了保证叶子节点 dis = 0
    scanf("%d %d", &n, &m);
    init();
    for (int i = 1; i <= n; i++)
        scanf("%d", &heap[i]);
    for (int opt, x, y; m; m--) {
        scanf("%d", &opt);
        if (opt == 1) {
            scanf("%d %d", &x, &y);
            if (del[x] || del[y])
                continue;
            x = find(x), y = find(y);
            if (x != y) 
                fa[x] = fa[y] = Merge(x, y);
        } else {
            scanf("%d", &x);
            if (del[x]) {
                printf("-1\n");
                continue;
            }
            x = find(x);
            printf("%d\n", heap[x]);
            pop(x);
        }
    }
    return 0;
}