算法与数据结构系列之[并查集-中]

上篇介绍了并查集的基本实现，这篇介绍几种并查集的优化方法。

1.基于size优化：

上一篇当中树实现并查集的方法中对要合并的两个元素所在的树的形状没有做任何的判断，合并的过程中可能不断增加树的高度，使查找的性能变差，甚至在极端情况下，极有可能使树退化成链表结构，使查询的时间复杂度退化到O(n)。

图一

那么该如何进行优化呢？首先我们维护一个数组，存放每棵树的元素的个数，每次合并时先将要合并的两个元素对应的树的元素进行比较，把树的元素少的节点指向树的元素多的节点上。

图二

上图，如果要将6和9合并，在不比较树的元素个数的情况下，可能合并的结果如下图所示：

图三

如果比较树的元素的个数，合并的结果如下图所示，树的高度和上图比小1

图四

代码实现：

public class UnionFind3 implements UF {
    int[] parent;
    int[] sz; //sz[i] 表示以i为根节点的元素色个数
    public UnionFind3(int size){
        parent = new int[size];
        sz = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            sz[i] = 1;
        }
    }

    @Override
    public int getSize() {
        return parent.length;
    }

    //查找i对应的集合编号
    //时间复杂度为O（h）,h为树的高度
    private int find(int i){
        if(i < 0 || i>= parent.length)
            throw new IllegalArgumentException("非法索引");
        while (i != parent[i])
            i = parent[i];
        return i;
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    //合并操作
    //时间复杂度为O（h）,h为树的高度
    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if(pRoot == qRoot)
            return;
        //根据两个元素所在的树的元素个数不同判断合并方向
        //将元素个数少的集合合并到元素个数多的集合
        if(sz[pRoot] < sz[qRoot]){
            parent[pRoot] = qRoot;
            sz[qRoot] += sz[pRoot];
        }else {
            parent[qRoot] =pRoot;
            sz[pRoot] += sz[qRoot];
        }
    }
}

大致测一下性能，和没优化之前比较。

测试代码：

public class Test {
    private static double testUF(UF uf,int m){
        int size = uf.getSize();
        Random random = new Random();

        long startTime = System.nanoTime();

        for (int i = 0; i < m; i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.unionElements(a,b);
        }

        for (int i = 0; i < m; i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.isConnected(a,b);
        }

        long endTime = System.nanoTime();

        return (endTime - startTime) / 1000000000.0;
    }

    public static void main(String[] args) {
        int size = 100000;
        int m = 100000;
        UnionFind1 unionFind1 = new UnionFind1(size);
        System.out.println("UnionFind1: " + testUF(unionFind1,m) + " s");
        UnionFind2 unionFind2 = new UnionFind2(size);
        System.out.println("UnionFind2: " + testUF(unionFind2,m) + " s");
        UnionFind3 unionFind3 = new UnionFind3(size);
        System.out.println("UnionFind3: " + testUF(unionFind3,m) + " s");

        /*UnionFind4 unionFind4 = new UnionFind4(size);
        System.out.println("UnionFind4: " + testUF(unionFind4,m) + " s");
        UnionFind5 unionFind5 = new UnionFind5(size);
        System.out.println("UnionFind5: " + testUF(unionFind5,m) + " s");
        UnionFind6 unionFind6 = new UnionFind6(size);
        System.out.println("UnionFind6: " + testUF(unionFind6,m) + " s");*/
    }
}

执行结果

图五

由执行结果大致可以清楚优化后的速度比优化前要快很多，所以这种优化是很有必要的。

2.基于rank的优化

上面基于size的优化看似没有问题，性能也较优化前提升了不少，其实还是有问题的，有的时候以树的元素个数为判断标准会出现这样的问题：深度大的节点指向了深度小的节点，从而使合并后的树的深度更大。

图六 图七

那么，基于上述的问题，可以用基于rank的优化来解决，在介绍压缩路径之前，可以先将rank理解为树的深度，通过一个数组来维护树的深度，每次合并前都先比较要合并的两个元素所在的树的深度的大小，将深度小的节点指向深度大的节点，以达到使合并后的树的深度不至于过大的目的。

图七

上面后一种方法比前一中方法合并后树的深度小1，当数据量很大时，这样的优化还是能提升一些性能的。

代码实现

public class UnionFind4 implements UF {
    int[] parent;
    int[] rank; //rank[i] 表示以i为根节点的集合所表示的树的层数
    public UnionFind4(int size){
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    @Override
    public int getSize() {
        return parent.length;
    }

    //查找i对应的集合编号
    //时间复杂度为O（h）,h为树的高度
    private int find(int i){
        if(i < 0 || i>= parent.length)
            throw new IllegalArgumentException("非法索引");
        while (i != parent[i])
            i = parent[i];
        return i;
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    //合并操作
    //时间复杂度为O（h）,h为树的高度
    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if(pRoot == qRoot)
            return;
        //根据两个元素所在的树的rank不同判断合并方向
        //将元rank低的集合合并到rank高的集合
        if(rank[pRoot] < rank[qRoot]){
            parent[pRoot] = qRoot;
        }
        else if (rank[qRoot] < rank[pRoot]){
            parent[qRoot] =pRoot;
        }
        else{  //rank[pRoot] == rank[qRoot]   以pRoot和qRoot为根节点的两棵树层数一样时,合并时可以将任意一个合并到另一个即可
            parent[pRoot] = qRoot;
            rank[qRoot] += 1;  //合并完成后层数加1
        }
    }
}

性能测试
代码同上，加上几句即可（测试数据增大，比较更明显）

int size = 10000000;
int m = 10000000;
System.out.println("UnionFind4: " + testUF(unionFind4,m) + " s");
UnionFind5 unionFind5 = new UnionFind5(size);

执行结果：

图八 本人微信公众号，点关注，不迷路