线段树、Trie和并查集03：并查集

并查集，又称Union Find，和之前的树结构不同，并查集的指针由孩子指向父亲

常用于解决连接问题，比如网络中节点间的连接状态

对一组数据，并查集主要支持合并和查询两个动作，unionElement(p, q)和isConnected(q, p)

数组实现并查集（Quick Find）

效率低，不推荐

/**
 * 定义一个并查集接口
 */
interface UF{

    int getSize();
    boolean isConnected(int p, int q);
    void unionElement(int p, int q);
}

/**
 * 该版本只是用数组模拟了并查集的实现，查询操作很快，但是合并操作却很慢
 * find()方法的时间复杂度为O(1)，而unionElement()方法的时间复杂度为O(n)
 */
class UnionFind implements UF{

    /**
     * id数组存放所有的元素，其值为该元素所属的集合ID
     * 初始时每个元素的ID都不一样
     */
    int [] id;

    public UnionFind(int size){

        id = new int[size];

        for (int i = 0; i < id.length; i++) {
            id[i] = i;
        }
    }

    @Override
    public int getSize(){

        return id.length;
    }

    /**
     * 查询元素p所属的集合ID
     * 时间复杂度为O(1)
     */
    private int find(int p){

        if (p < 0 || p >= id.length){
            throw new IllegalArgumentException("索引值非法");
        }

        return id[p];
    }

    /**
     * 判断两个元素是否是连接的，即集合ID是否相同
     */
    @Override
    public boolean isConnected(int p, int q){

        return find(p) == find(q);
    }

    /**
     * 将两种不同集合的所有元素合并到同一种集合
     * 时间复杂度为O(n)
     */
    @Override
    public void unionElement(int p, int q){

        int pID = id[p];
        int qID = id[q];

        if (pID == qID){
            return;
        }
        else {

            for (int i = 0; i < id.length; i++) {

                if (id[i] == pID){
                    id[i] = qID;
                }
            }
        }
    }
}

树结构实现并查集（Quick Union）

将元素看作是节点（不用真正的使用节点类），用树结构实现，指针由孩子指向父亲

interface UF{

    int getSize();
    boolean isConnected(int p, int q);
    void unionElement(int p, int q);
}

/**
 * 使用数组模拟树结构实现并查集，但是不使用节点类
 * find()和unionElement()方法的时间复杂度为O(h)
 */
class UnionFind implements UF{

    /**
     * parent()方法存放所有的元素，其值为所在树的根节点（指针由下往上）
     * 初始时每个元素都是一颗树，只有一个根节点
     */
    int[] parent;

    public UnionFind(int size){

        parent = new int[size];

        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }
    }

    @Override
    public int getSize(){

        return parent.length;
    }

    /**
     * 查询元素p的根节点，判断条件是当前节点的下一个节点是否是自身
     * 时间复杂度为O(h)
     */
    private int find(int p){

        if (p < 0 || p >= parent.length){
            throw new IllegalArgumentException("索引值非法");
        }

        while (parent[p] != p){
            p = parent[p];
        }

        return p;
    }

    @Override
    public boolean isConnected(int p, int q){

        return find(p) == find(q);
    }

    /**
     * 合并p和q两种集合，就是让p的根节点指向q
     * 时间复杂度为O(h)
     */
    @Override
    public void unionElement(int p, int q){

        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot){
            return;
        }
        else {
            parent[pRoot] = qRoot;
        }
    }
}

基于size的优化

存在的问题：当运行的次数很大时，树结构的深度也会很深，甚至会退化成链表，而isConnected()方法的时间复杂度相对较高，会导致其性能下降，甚至不如数组实现的性能

优化空间：合并集合的同时考虑当前集合的元素个数，让个数少的树指向个数多的树，避免树太深

interface UF{

    int getSize();
    boolean isConnected(int p, int q);
    void unionElement(int p, int q);
}

class UnionFind implements UF{

    /**
     * 定义一个nums[]数组存放每棵树的节点个数，初始时都是1
     */
    int[] parent;
    int[] nums;

    public UnionFind(int size){

        parent = new int[size];
        nums = new int[size];

        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            nums[i] = 1;
        }
    }

    @Override
    public int getSize(){

        return parent.length;
    }

    private int find(int p){

        if (p < 0 || p >= parent.length){
            throw new IllegalArgumentException("索引值非法");
        }

        while (parent[p] != p){
            p = parent[p];
        }

        return p;
    }

    @Override
    public boolean isConnected(int p, int q){

        return find(p) == find(q);
    }

    /**
     * 将元素个数少的集合合并到元素个数多的集合，避免树的链表化
     */
    @Override
    public void unionElement(int p, int q){

        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot){
            return;
        }
        else {

            if (nums[pRoot] <= nums[qRoot]){

                parent[pRoot] = qRoot;
                nums[qRoot] += nums[pRoot];
            }
            else {

                parent[qRoot] = pRoot;
                nums[pRoot] += nums[qRoot];
            }
        }
    }
}

基于rank的优化

存在问题：虽然基于size的优化已经大大提高了并查集的性能，但是其存在一个不理想的情况，那就是如果一棵树高度很高但是元素个数少，其会指向元素个数多但是高度很低的树，这样又增加了树的最大深度

优化空间：更合理的做法是让高度低的树指向高度高的树

interface UF{

    int getSize();
    boolean isConnected(int p, int q);
    void unionElement(int p, int q);
}

class UnionFind implements UF{

    /**
     * 定义一个rank[]数组存放每棵树的高度，初始时都是1
     */
    int[] parent;
    int[] rank;

    public UnionFind(int size){

        parent = new int[size];
        rank = new int[size];

        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    @Override
    public int getSize(){

        return parent.length;
    }

    private int find(int p){

        if (p < 0 || p >= parent.length){
            throw new IllegalArgumentException("索引值非法");
        }

        while (parent[p] != p){
            p = parent[p];
        }

        return p;
    }

    @Override
    public boolean isConnected(int p, int q){

        return find(p) == find(q);
    }

    /**
     * 让高度低的树指向高度高的树
     * 当两棵树高度相等的时候，让一颗指向另一颗，然后更新高度值
     */
    @Override
    public void unionElement(int p, int q){

        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot){
            return;
        }
        else {

            if (rank[pRoot] < rank[qRoot]){
                parent[pRoot] = qRoot;
            }
            else if (rank[pRoot] > rank[qRoot]){
                parent[qRoot] = pRoot;
            }
            else {

                parent[pRoot] = qRoot;
                rank[qRoot]++;
            }
        }
    }
}

路径压缩优化（Path Compression）

在每次查找时，如果当前节点的父亲节点不是自身，那就指向爷爷节点，然后再向下寻找，直到根节点，这样整棵树的高度就会进一步降低

此时可以解释为什么rank优化不能称为height优化，因为在路径压缩中，高度一直在变，而排名不会变，所以称为rank更恰当

interface UF{

    int getSize();
    boolean isConnected(int p, int q);
    void unionElement(int p, int q);
}

class UnionFind implements UF{

    int[] parent;
    int[] rank;

    public UnionFind(int size){

        parent = new int[size];
        rank = new int[size];

        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    @Override
    public int getSize(){

        return parent.length;
    }

    private int find(int p){

        if (p < 0 || p >= parent.length){
            throw new IllegalArgumentException("索引值非法");
        }

        /**
         * 只添加一句，让当前节点指向爷爷节点
         */
        while (parent[p] != p){

            parent[p] = parent[parent[p]];
            p = parent[p];
        }

        return p;
    }

    @Override
    public boolean isConnected(int p, int q){

        return find(p) == find(q);
    }

    @Override
    public void unionElement(int p, int q){

        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot){
            return;
        }
        else {

            if (rank[pRoot] < rank[qRoot]){
                parent[pRoot] = qRoot;
            }
            else if (rank[pRoot] > rank[qRoot]){
                parent[qRoot] = pRoot;
            }
            else {

                parent[pRoot] = qRoot;
                rank[qRoot]++;
            }
        }
    }
}

最终优化（所有子节点直接指向根节点）

让所有子节点都直接指向根节点，树的高度始终只有两层

递归的寻找到每个节点的根节点，也会消耗相当多的性能，时间复杂度比路径压缩要高点

interface UF{

    int getSize();
    boolean isConnected(int p, int q);
    void unionElement(int p, int q);
}

class UnionFind implements UF{

    int[] parent;
    int[] rank;

    public UnionFind(int size){

        parent = new int[size];
        rank = new int[size];

        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    @Override
    public int getSize(){

        return parent.length;
    }

    private int find(int p){

        if (p < 0 || p >= parent.length){
            throw new IllegalArgumentException("索引值非法");
        }

        /**
         * 递归的查找到一个节点的根节点
         * 让其直接指向根节点，这样所有的节点都指向了根节点，树的高度只有两层
         */
        if (parent[p] != p){
            parent[p] = find(parent[p]);
        }

        return parent[p];
    }

    @Override
    public boolean isConnected(int p, int q){

        return find(p) == find(q);
    }

    @Override
    public void unionElement(int p, int q){

        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot){
            return;
        }
        else {

            if (rank[pRoot] < rank[qRoot]){
                parent[pRoot] = qRoot;
            }
            else if (rank[pRoot] > rank[qRoot]){
                parent[qRoot] = pRoot;
            }
            else {

                parent[pRoot] = qRoot;
                rank[qRoot]++;
            }
        }
    }
}

六种实现的性能比较

import java.util.Random;

public class Algorithm {

    public static void main(String[] args) {

        int[] scale = {10000, 100000};
        int count = 100000;

        for (int n : scale){

            System.out.println("测试用例规模为" + n);

            UnionFind unionFind = new UnionFind(n);
            UnionFindOptimized unionFindOptimized = new UnionFindOptimized(n);
            UnionFindOptimized2 unionFindOptimized2 = new UnionFindOptimized2(n);
            UnionFindOptimized3 unionFindOptimized3 = new UnionFindOptimized3(n);
            UnionFindOptimized4 unionFindOptimized4 = new UnionFindOptimized4(n);
            UnionFindOptimized5 unionFindOptimized5 = new UnionFindOptimized5(n);

            System.out.println("数组实现并查集：" + test(unionFind, count) + "秒");
            System.out.println("树实现并查集：" + test(unionFindOptimized, count) + "秒");
            System.out.println("优化size实现并查集：" + test(unionFindOptimized2, count) + "秒");
            System.out.println("优化rank实现并查集：" + test(unionFindOptimized3, count) + "秒");
            System.out.println("路径压缩优化实现并查集：" + test(unionFindOptimized4, count) + "秒");
            System.out.println("最终优化实现并查集：" + test(unionFindOptimized5, count) + "秒");

            System.out.println();
        }
    }

    public static double test(UF uf, int count){

        int size = uf.getSize();
        Random random = new Random();

        long startTime = System.nanoTime();

        for (int i = 0; i < count; i++) {

            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.unionElement(a, b);
        }

        for (int i = 0; i < count; i++) {

            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.isConnected(a, b);
        }

        long endTime = System.nanoTime();

        return (endTime - startTime) / 1000000000.0;
    }
}

/**
 * 最终优化
 */
interface UF{

    int getSize();
    boolean isConnected(int p, int q);
    void unionElement(int p, int q);
}

class UnionFindOptimized5 implements UF{

    int[] parent;
    int[] rank;

    public UnionFindOptimized5(int size){

        parent = new int[size];
        rank = new int[size];

        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    @Override
    public int getSize(){

        return parent.length;
    }

    private int find(int p){

        if (p < 0 || p >= parent.length){
            throw new IllegalArgumentException("索引值非法");
        }

        if (parent[p] != p){
            parent[p] = find(parent[p]);
        }

        return parent[p];
    }

    @Override
    public boolean isConnected(int p, int q){

        return find(p) == find(q);
    }

    @Override
    public void unionElement(int p, int q){

        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot){
            return;
        }
        else {

            if (rank[pRoot] < rank[qRoot]){
                parent[pRoot] = qRoot;
            }
            else if (rank[pRoot] > rank[qRoot]){
                parent[qRoot] = pRoot;
            }
            else {

                parent[pRoot] = qRoot;
                rank[qRoot]++;
            }
        }
    }
}

/**
 * 路径压缩优化
 */
class UnionFindOptimized4 implements UF{

    int[] parent;
    int[] rank;

    public UnionFindOptimized4(int size){

        parent = new int[size];
        rank = new int[size];

        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    @Override
    public int getSize(){

        return parent.length;
    }

    private int find(int p){

        if (p < 0 || p >= parent.length){
            throw new IllegalArgumentException("索引值非法");
        }

        /**
         * 只添加一句，让当前节点指向爷爷节点
         */
        while (parent[p] != p){

            parent[p] = parent[parent[p]];
            p = parent[p];
        }

        return p;
    }

    @Override
    public boolean isConnected(int p, int q){

        return find(p) == find(q);
    }

    @Override
    public void unionElement(int p, int q){

        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot){
            return;
        }
        else {

            if (rank[pRoot] < rank[qRoot]){
                parent[pRoot] = qRoot;
            }
            else if (rank[pRoot] > rank[qRoot]){
                parent[qRoot] = pRoot;
            }
            else {

                parent[pRoot] = qRoot;
                rank[qRoot]++;
            }
        }
    }
}

/**
 * 基于rank优化
 */
class UnionFindOptimized3 implements UF{

    int[] parent;
    int[] rank;

    public UnionFindOptimized3(int size){

        parent = new int[size];
        rank = new int[size];

        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    @Override
    public int getSize(){

        return parent.length;
    }

    private int find(int p){

        if (p < 0 || p >= parent.length){
            throw new IllegalArgumentException("索引值非法");
        }

        while (parent[p] != p){
            p = parent[p];
        }

        return p;
    }

    @Override
    public boolean isConnected(int p, int q){

        return find(p) == find(q);
    }

    @Override
    public void unionElement(int p, int q){

        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot){
            return;
        }
        else {

            if (rank[pRoot] < rank[qRoot]){
                parent[pRoot] = qRoot;
            }
            else if (rank[pRoot] > rank[qRoot]){
                parent[qRoot] = pRoot;
            }
            else {

                parent[pRoot] = qRoot;
                rank[qRoot]++;
            }
        }
    }
}

/**
 * 基于size优化
 */
class UnionFindOptimized2 implements UF{

    int[] parent;
    int[] nums;

    public UnionFindOptimized2(int size){

        parent = new int[size];
        nums = new int[size];

        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            nums[i] = 1;
        }
    }

    @Override
    public int getSize(){

        return parent.length;
    }

    private int find(int p){

        if (p < 0 || p >= parent.length){
            throw new IllegalArgumentException("索引值非法");
        }

        while (parent[p] != p){
            p = parent[p];
        }

        return p;
    }

    @Override
    public boolean isConnected(int p, int q){

        return find(p) == find(q);
    }

    @Override
    public void unionElement(int p, int q){

        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot){
            return;
        }
        else {

            if (nums[pRoot] <= nums[qRoot]){

                parent[pRoot] = qRoot;
                nums[qRoot] += nums[pRoot];
            }
            else {

                parent[qRoot] = pRoot;
                nums[pRoot] += nums[qRoot];
            }
        }
    }
}

/**
 * 树结构实现
 */
class UnionFindOptimized implements UF{

    int[] parent;

    public UnionFindOptimized(int size){

        parent = new int[size];

        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }
    }

    @Override
    public int getSize(){

        return parent.length;
    }

    private int find(int p){

        if (p < 0 || p >= parent.length){
            throw new IllegalArgumentException("索引值非法");
        }

        while (parent[p] != p){
            p = parent[p];
        }

        return p;
    }

    @Override
    public boolean isConnected(int p, int q){

        return find(p) == find(q);
    }

    @Override
    public void unionElement(int p, int q){

        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot){
            return;
        }
        else {
            parent[pRoot] = qRoot;
        }
    }
}

/**
 * 数组实现
 */
class UnionFind implements UF{

    int [] id;

    public UnionFind(int size){

        id = new int[size];

        for (int i = 0; i < id.length; i++) {
            id[i] = i;
        }
    }

    @Override
    public int getSize(){

        return id.length;
    }

    private int find(int p){

        if (p < 0 || p >= id.length){
            throw new IllegalArgumentException("索引值非法");
        }

        return id[p];
    }

    @Override
    public boolean isConnected(int p, int q){

        return find(p) == find(q);
    }

    @Override
    public void unionElement(int p, int q){

        int pID = id[p];
        int qID = id[q];

        if (pID == qID){
            return;
        }
        else {

            for (int i = 0; i < id.length; i++) {

                if (id[i] == pID){
                    id[i] = qID;
                }
            }
        }
    }
}