「并查集」专题 5:并查集第 4 版 quick-union 基于 rank 的优化


「并查集」专题 5:并查集第 4 版 quick-union 基于 rank 的优化

重点提示:基于 rank 的优化是使用得更多的,因为这样做更合理一些。

但是维护数组 rank 的定义是相对麻烦的,通常的做法就是不维护,只是把数组 rank 作为两个集合合并的参考,即使是错的,也比随机合并的结果好。

使用 size 来决定将哪个结点的根指向另一个结点的根,其实并不太合理,但并不能说不正确,因为谁的根指向谁的根,其实都没有错,下面就是一个特殊的情况。

![高级数据结构:并查集-8](https://liweiwei1419.gitee.io/images/algorithms/union-find-set/基于 size 合并不合理的地方.jpg)

因为我们总是期望这棵树的高度比较低,在这种情况下,我们在 find 的时候,就能通过很少的步数来找到根结点,进而提高 find 的效率。为此,我们引入 rank 数组,其定义是: rank[i] 表示以第 i 个元素为根的树的高度。

Java 代码:

public class UnionFind4 implements IUnionFind {

    private int[] parent;

    private int count;

    // 以下标为 i 的元素为根结点的树的深度(最深的那个深度)
    private int[] rank;

    public UnionFind4(int n) {
        this.count = n;
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            // 初始化时,所有的元素只包含它自己,只有一个元素,所以 rank[i] = 1
            rank[i] = 1;
        }
    }

    @Override
    public String versionName() {
        return "并查集的第 4 个版本,基于 parent 数组,quick-union,基于 rank";
    }

    // 返回下标为 p 的元素的根结点
    @Override
    public int find(int p) {
        while (p != parent[p]) {
            p = parent[p];
        }
        return p;
    }

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


    @Override
    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        // 这一步是与第 3 版不同的地方
        if (rank[pRoot] > rank[qRoot]) {
            parent[qRoot] = pRoot;
        } else if (rank[pRoot] < rank[qRoot]) {
            parent[pRoot] = qRoot;
        } else {
            parent[qRoot] = pRoot;
            rank[pRoot]++;
        }
        // 每次 union 以后,连通分量减 1
        count--;
    }
}

文章作者: liweiwei1419
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei1419 !
评论
 上一篇
「并查集」专题 6:并查集第 5 版 quick-union 基于路径压缩的非递归实现 「并查集」专题 6:并查集第 5 版 quick-union 基于路径压缩的非递归实现
「并查集」专题 6:并查集第 5 版 quick-union 基于路径压缩的非递归实现 重点提示:这一版代码用得最多。因为好理解,且代码量较少。 只用理解这一句即可 parent[p] = parent[parent[p]];,可以称之为「
下一篇 
「并查集」专题 4:并查集第 3 版 quick-union 基于 size 的优化 「并查集」专题 4:并查集第 3 版 quick-union 基于 size 的优化
「并查集」专题 4:并查集第 3 版 quick-union 基于 size 的优化 重点提示:这一版「并查集」代码是最基本的「并查集」,我们需要学习思想,核心思想是「代表元法」,以「树」的「根结点」作为代表元。 后续我们介绍这一版代码的两
  目录