可并堆之左偏树学习笔记

博客版本

参考：hsfzLZH1 的博客及代码启示

左偏树

模版题：Luogu3377。

由于朴素堆的合并操作可能会退化到 $O (n)$ ，所以我们需要通过一些方式维护合并操作，左偏树就是其中之一。

一些定义

该部分改编自 hsfzLZH1 的博客

外结点 ：左儿子或右儿子是空结点的结点（首先左偏树是一个堆，堆是一棵二叉树）。

距离：一个结点 $x$ 的距离 $d i s_{x}$ 定义为其子树中与结点 $x$ 最近的外结点到 $x$ 的距离。特别地，定义空结点的距离为 $- 1$ 。

基本性质

堆性质：与普通堆相同，以小根堆为例，其满足每个结点的关键字一定小于等于其左右儿子。
左偏性：对于每个结点 $x$ ，有 $d i s_{l s} \geq d i s_{r s}$ （ $l s$ 为 $x$ 结点的左儿子， $r s$ 为 $x$ 结点的右儿子，下同）

容易发现，左偏树的每一个儿子的左子树的结点数量一定不小于右子树的结点数量。这为我们的合并操作提供了便利。

基本结论

$d i s_{x} = d i s_{r s} + 1$ 。
从根结点开始，一直往右儿子走，走到空结点的复杂度是 $O (\log n)$ 。

知道这两个结论就足够了。

如果你还有兴趣的话，这里补充一个性质：距离为 $n$ 的左偏树至少有 $2^{n + 1} - 1$ 个结点。此时该左偏树的形态是一棵满二叉树。

合并操作

合并两棵分别以 $x, y$ 为根结点的左偏树（我们定义该操作为 $merge (x, y)$ ）时，我们每次先将 $x$ 和 $y$ 的关键字进行比较，以小根堆为例，我们将 $x$ 和 $y$ 中关键字小的那个点作为新的根（具体的，我们记 $x$ 的关键字为 $v_{x}$ ， $y$ 同理，如果 $v_{x} < v_{y}$ ，则将 $x$ 作为根结点，否则交换 $x, y$ ，将新的 $x$ ，即原来的 $y$ 作为根结点），然后执行 $merge (r s, y)$ （ $r s$ 为 $x$ 结点的右儿子）。

在合并过程中，如果我们发现以 $x$ 为根的子树不满足左偏性的话，交换 $l s$ 与 $r s$ 即可。

容易发现合并后的树后的树仍然满足堆性质和左偏性，且该操作的复杂度是 $O (\log n)$ ，这样我们就成功实现目的了。

维护结点所在左偏树的根结点

经常地，题目会给定一个点，需要你求出其所在左偏树的根节点再进行后续操作。

我们可以记录每一个的父亲节点 $f a_{x}$ ，然后暴力跳父亲结点。但是这个操作的复杂度可能到达 $O (n)$ ，是不可接受的。类似并查集的，我们可以采用路径压缩来求一个结点所在左偏树的根节点，从而将复杂度降至 $O (\log n)$ 。

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

这时候我们需要对合并操作和删除操作进行操作。

删除一个点，就是对于一个点合并其左右儿子即可，非常简单。

合并结点 $x, y$ 时，我们只需要 rt[x]=rt[y]=merge(x,y)。
删除结点 $x$ 时，我们只需要 rt[ls[x]]=rt[rs[x]]=rt[x]=merge(ls[x],rs[x])

注意，再删除操作时，我们需要将 $r t_{x}$ 的值也赋成新值，因为这棵子树中，可能还有一些点的 $r t$ 是指向 $x$ 结点的，我们必须要保证这些点能找到正确的根节点。

一些简单的其他操作

插入一个值：等价于与一棵只有一个结点的树合并，唯一结点的权值等于插入的值。
求最小值：直接返回根结点的值即可。
删除最小值：合并根节点的左右儿子即可（记得删除时需要维护一些需要维护的信息）。

简单地说，左偏树就是一个将合并操作复杂度降至 $O (\log n)$ 的堆。

几道练手题

Luogu2713 罗马游戏纯模板，学会左偏树后可以直接解决。

Luogu1552 [APIO2012] 派遣有一定思维难度的一道可并堆，利用可并堆解决问题的一道典例。

Luogu1456 Monkey King 可并堆题，但是有一个比较有趣的操作，可以锻炼对可并堆的变换能力，比较简单。

代码

Luogu3377 【模板】左偏树（可并堆）

 #include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct Heap {
    int val, id, ls, rs;
    bool operator <(const Heap &x)const {
        if (val == x.val) return id < x.id;
        return val < x.val;
    };
} tree[N];
int n, m, fa[N], fl[N], dis[N];
inline int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}
inline int merge(int x, int y) {
    if (!x || !y) return x + y;
    if (tree[y] < tree[x]) swap(x, y);
    tree[x].rs = merge(tree[x].rs, y);
    if (dis[tree[x].ls] < dis[tree[x].rs]) swap(tree[x].ls, tree[x].rs);
    dis[x] = dis[tree[x].rs] + 1;
    return x;
}
int main() {
    dis[0] = -1;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &tree[i].val);
        tree[i].id = i; fa[i] = i;
    }
    for (int i = 1, opt, x, y; i <= m; i++) {
        scanf("%d%d", &opt, &x);
        if (opt == 1) {
            scanf("%d", &y);
            if (fl[x] || fl[y]) continue;
            x = find(x); y = find(y);
            if (x != y) fa[x] = fa[y] = merge(x, y);
        }
        else {
            if (fl[x]) {
                printf("-1\n");
                continue;
            }
            x = find(x);
            printf("%d\n", tree[x].val);
            fl[x] = true;
            fa[tree[x].ls] = fa[tree[x].rs] = fa[x] = merge(tree[x].ls, tree[x].rs);
        }
    }
    return 0;
}

左偏树