左偏树 学习笔记

作者: xht37 分类: 笔记 发布时间: 2020-02-29 21:23

点击数:72

左偏树是一种可并堆,具有堆的性质,同时支持快速合并。

定义和性质

对于一棵二叉树,定义一个节点的 $\mathrm{dist}$ 为这个点到它的子树中距离它最近的叶子的路径上的节点数。一个空节点的 $\mathrm{dist}$ 为 $0$,叶子节点的 $\mathrm{dist}$ 为 $1$,根的 $\mathrm{dist}$ 不超过 $\lceil\log (n+1)\rceil$。

左偏树是一棵二叉树,它不仅具有堆(本文为小根堆)的性质,并且是「左偏」的:每个节点左儿子的 $\mathrm{dist}$ 都大于等于右儿子的 $\mathrm{dist}$。因此,左偏树每个节点的 $\mathrm{dist}$ 都等于其右儿子的 $\mathrm{dist}$ 加一。

核心操作:合并

合并两个堆时,由于要满足堆性质,先取值较小的那个根作为合并后堆的根节点,然后将这个根的左儿子作为合并后堆的左儿子,递归地合并其右儿子与另一个堆,作为合并后的堆的右儿子。为了满足左偏性质,合并后若左儿子的 $\mathrm{dist}$ 小于右儿子的 $\mathrm{dist}$,就交换两个儿子,时间复杂度 $\mathcal O(\log n)$。

int merge(int x, int y) {
    if (!x || !y) return x | y;
    if (t[x].x > t[y].x) swap(x, y);
    t[t[x].r=merge(t[x].r,y)].f = x;
    if (t[t[x].r].d > t[t[x].l].d) swap(t[x].l, t[x].r);
    t[x].d = t[t[x].r].d + 1;
    return x;
}

【模板】P3377 【模板】左偏树(可并堆)

由于并查集需要路径压缩才能保证时间复杂度,因此这题需要将删掉的点重新指向合并后的新根,因此有些细节要注意。

const int N = 1e5 + 7;
int n, m, f[N];
bool v[N];
struct T {
    int x, l, r, f, d;
} t[N];

int get(int x) {
    return x == f[x] ? x : (f[x] = get(f[x]));
}

int merge(int x, int y) {
    if (!x || !y) return x | y;
    if (t[x].x > t[y].x || (t[x].x == t[y].x && x > y)) swap(x, y);
    t[t[x].r=merge(t[x].r,y)].f = x;
    if (t[t[x].l].d < t[t[x].r].d) swap(t[x].l, t[x].r);
    t[x].d = t[t[x].r].d + 1;
    return f[y] = x;
}

int main() {
    rd(n), rd(m);
    for (int i = 1; i <= n; i++) rd(t[i].x), t[i].d = 1, f[i] = i;
    for (int i = 1, o, x, y; i <= m; i++) {
        rd(o), rd(x);
        if (o == 1) {
            rd(y);
            if (v[x] || v[y]) continue;
            x = get(x), y = get(y);
            if (x != y) merge(x, y);
        } else if (v[x]) print(-1);
        else {
            x = get(x), v[x] = 1, print(t[x].x);
            f[x] = f[t[x].l] = f[t[x].r] = merge(t[x].l, t[x].r);
        }
    }
    return 0;
}

参考资料

发表评论

电子邮件地址不会被公开。 必填项已用*标注