左偏树

左偏树是一种可并的堆，并且合并复杂度O(logn)

左偏树是一种性质很特殊的数，它的复杂度之所以能达到logn就是因为左偏的性质。

外节点：我们规定左子树为空或者右子树为空的节点为外节点，但是不能两个都为空。

对于一个节点x，我们定义dis[x]为子树中最近的外节点到它的距离。定义空节点距离为-1.

性质1：左偏树是一种堆，那么肯定满足堆的性质，如果维护的是小顶堆，那么就有x在x的子树中权值最小（因为x是子树的堆顶）。

性质2：左偏性质，对于每个节点都有,dis[lc] >= dis[rc].即左边的链长度较长。

因为有了左偏性质，合并的时候我们才能做到logn复杂度，其实就有点类似启发式合并。

这里有个细节，如果我们要删堆顶元素，但是如果光置为空，那么原先rt = 堆顶的元素的根就变成了空。

所以，我们把顶堆只想堆顶的左右儿子合并后的堆顶，这样就可以了。

https://www.luogu.com.cn/problem/P3377

import java.io.*;

public class Main {


    public static int N = 100005;
    static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

    static int readInt() throws IOException {
        cin.nextToken();
        return (int)cin.nval;
    }
    public static class LeftTree {
        int lc[] = new int[N];
        int rc[] = new int[N];
        int dis[] = new int[N];
        int val[] = new int[N];
        int rt[] = new int[N];
        int id[] = new int[N];
        boolean del[] = new boolean[N];

        public void input(int n) throws IOException {
            dis[0] = -1;
            for(int i = 1;i <= n;++i) {
                int x = readInt();
                rt[i] = i;
                val[i] = x;
                id[i] = i;
            }
        }

        public int merge(int x,int y) {
            if(x == 0 || y == 0) return x + y;
            if(val[x] > val[y] || val[x] == val[y] && id[x] > id[y]) {//小顶堆
                int tmp = x;
                x = y;
                y = tmp;
            }
            rc[x] = merge(rc[x],y);
            if(dis[lc[x]] < dis[rc[x]]) {//维持左偏树特性
                int tmp = rc[x];
                rc[x] = lc[x];
                lc[x] = tmp;
            }
            dis[x] = dis[rc[x]] + 1;
            return x;
        }

        public boolean check(int x) {
            if(del[x] == true) return true;
            else return false;
        }
        public int find(int x) {
            if(x == rt[x]) return x;
            else return rt[x] = find(rt[x]);
        }
        public void mergeRoot(int x,int y) {
            int xx = find(x);
            int yy = find(y);
            if(xx != yy) rt[xx] = rt[yy] = merge(xx,yy);
        }
    };


    public static void main(String[] args) throws IOException {
        int n = readInt();
        int m = readInt();
        LeftTree leftTree = new LeftTree();
        leftTree.input(n);
        for(int i = 1;i <= m;++i) {
            int id = readInt();
            if(id == 1) {
                int x = readInt();
                int y = readInt();
                if(leftTree.check(x) || leftTree.check(y)) continue;
                leftTree.mergeRoot(x,y);
            }
            else {
                int x = readInt();
                if(leftTree.check(x)) {
                    out.println("-1");
                    continue;
                }
                x = leftTree.find(x);
                out.println(leftTree.val[x]);
                leftTree.del[x] = true;
                leftTree.rt[leftTree.lc[x]] = leftTree.rt[leftTree.rc[x]] = leftTree.rt[x] = leftTree.merge(leftTree.lc[x],leftTree.rc[x]);
            }
        }
        out.close();
    }

}

View Code

左偏树

推荐阅读