从零实现并查集，并逐步优化各版本中的问题。

概念

wiki:

In computer science, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that stores a collection of disjoint (non-overlapping) sets. Equivalently, it stores a partition of a set into disjoint subsets. It provides operations for adding new sets, merging sets (replacing them by their union), and finding a representative member of a set. The last operation makes it possible to find out efficiently if any two elements are in the same or different sets.

并查集是一种实现了数学中集合概念的数据结构。内部元素彼此不重复，因此我们可以很方便的使用数组来实现此结构（下标不重复）。

提供的功能包括：

  • 添加新的集合 init
  • 合并多个集合 union
  • 查找集合中的标识，也就是我们下述实现的树根 find

基于数组实现的 QuickFindUF

根据概念，我们可以基于数组实现一个并查集：

  1. 使用数组存储元素，下标标识元素，表示并查集的树；
  2. 元素值（数组值）相同，视为元素是连接的；
  3. union合并元素操作：将元素下标指向的值变成相同的；
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

public class QuickFindUF {

    /**
     * 数据集容量
     */
    int capacity;

    /**
     * 使用数组存储元素，
     */
    int[] elements;

    public QuickFindUF(int n) {
        this.capacity = n;
        this.elements = new int[n];
        for (int i = 0; i < elements.length; i++) {
            elements[i] = i;
        }
    }

    /**
     * 复杂度 O(n)
     */
    void union(int p, int q) {
        if (isConnected(p, q)) {
            return;
        }

        // 将p点以及连接的点，都指向 elements[q]
        for (int i = 0; i < elements.length; i++) {
            if (elements[i] == find(p)) {
                elements[i] = find(q);
            }
        }
    }

    int find(int i) {
        return elements[i];
    }

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

}

可以看到union操作复杂度为O(n)，我们需要优化。

以树根为中心的 QuickUF

  • 我们同样基于数组表示这棵并查集树，将数组指向尽可能组织起来；
  • 初始时每个元素指向自己，表示为一个根；
  • 查找指向时，沿着树一直向上查找根节点；
  • union合并时，将新节点指向原节点树根，由于union多个节点都指向树根，因此理论上树高远小于总数据量，因此效率提高；

修改点：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

    int[] parentArr;
        /**
     * 寻找i元素对应树根
     *
     * @param i 元素下标
     * @return 指向的树根
     */
    int find(int i) {
        // i保证不越界
        // 只要i在树上没到达树根，就一直往上走
        while (parentArr[i] != i) {
            i = parentArr[i];
        }
        return i;
    }
    /**
     * 将q节点指向的树根指向p的树根
     *
     * @param p 前序节点
     * @param q 后继节点
     */
    void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        parentArr[qRoot] = pRoot;
    }

实测下本版本效果并不太好。

QuickUF 中我们每次union时很可能会将一棵较高的树，并到一棵较低的树上，这样其实总的树高是变高了，复杂度因此而攀升，这也是实测下运行慢的主要原因。

判断子集元素数 SizeUF

本轮优化中 SizeUF 我们每次union都可以判断下集合元素数，每次将元素较少的树并到较多的树上，这样总的树高可以得到控制。

我们新增一个数组sizeArr来保存集合元素数，O(1)即能获取到树对应元素数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

public class SizeUF {

    /**
     * 并查集总数据量
     */
    int n;
    /**
     * 记录每个元素（实际是下标）对应父元素，根指向自己
     */
    int[] parentArr;
    /**
     * 记录每个元素（实际是下标）对应并集元素数量，供union时判断
     */
    int[] sizeArr;

    public SizeUF(int n) {
        this.n = n;
        this.parentArr = new int[n];
        this.sizeArr = new int[n];
        for (int i = 0; i < parentArr.length; i++) {
            parentArr[i] = i;
            sizeArr[i] = 1;
        }
    }

    int find(int i) {
        // 需保证i不越界
        while (parentArr[i] != i) {
            i = parentArr[i];
        }
        return i;
    }

    boolean isConnected(int p, int q) {
        if (p == q) {
            return true;
        }
        int pRoot = find(p);
        int qRoot = find(q);
        return pRoot == qRoot;
    }

    void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }

        if (sizeArr[pRoot] < sizeArr[qRoot]) {
            _union(qRoot, pRoot);
        } else {
            _union(pRoot, qRoot);
        }
    }

    /**
     * 将元素更少的树并到元素更多的树根上
     *
     * @param more 多元素树根
     * @param less 少元素树根
     */
    void _union(int more, int less) {
        parentArr[less] = parentArr[more];
        // 更少元素的树并到更多元素的树上，此时更少元素的根统一由 more 下标根负责，叠加less子树上的元素数
        sizeArr[more] += sizeArr[less];
    }
}

SizeUF 中根据树元素个数做了union时的优化，防止将更多元素的树合并到更少元素的树上，但是带来一个问题： 根据元素个数判断树高是不准确的。

能否继续优化？

判断集合树高 RankUF

find查找元素时，决定复杂度的是树高，因此 RankUF 中，我们优化 SizeUF size的逻辑。

sizeArr更名为：hArr。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

public class RankUF {
    /**
     * 并查集元素总量
     */
    int n;
    /**
     * 元素指向父的指针
     */
    int[] parentArr;
    /**
     * 当前节点（下标）对应集合树高，树高决定了find查找的复杂度，使用树高优化 SizeUF 带来的问题
     */
    int[] hArr;

    public RankUF(int n) {
        this.n = n;
        this.parentArr = new int[n];
        this.hArr = new int[n];
        for (int i = 0; i < parentArr.length; i++) {
            parentArr[i] = i;
            hArr[i] = 0;
        }
    }

    /**
     * 查找i下标所在集合的根
     */
    int find(int i) {
        // 保证i数组下标范围
        while (parentArr[i] != i) {
            i = parentArr[i];
        }
        return i;
    }

    /**
     * @param p p点下标
     * @param q q点下标
     * @return p所在树根==q所在树根时，表示p、q对应元素在同一集合内！
     */
    boolean isConnected(int p, int q) {
        if (p == q) {
            return true;
        }
        return find(p) == find(q);
    }

    void union(int p, int q) {

        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }

        if (hArr[pRoot] > hArr[qRoot]) {
            _union(pRoot, qRoot);
        } else if (hArr[pRoot] < hArr[qRoot]) {
            _union(qRoot, pRoot);
        } else {
            _union(pRoot, qRoot);
            hArr[pRoot] += 1;
        }
    }

    /**
     * 将更矮的树合并到更高的树上
     *
     * @param higherRoot 更高树根
     * @param lowerRoot  更矮树根
     */
    private void _union(int higherRoot, int lowerRoot) {
        parentArr[lowerRoot] = higherRoot;
    }
}

RankUF 中根据树高来精确判断union时的策略。但是在极端情况下，树仍然会很高，树有可能变矮吗？

当然可以！

路径压缩 CompressRankUF

我们可以使用路径压缩的方式将树高压短。

CompressRankUF 通过在查询数据时将树高一步步压缩（子节点的父直接指向根节点），以此提高了后续数据查询、合并时的效率。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

public class CompressRankUF {

    /**
     * 数据规模
     */
    int n;
    /**
     * 各元素父节点指针
     */
    int[] parentArr;
    /**
     * 树高
     */
    int[] rankArr;

    public CompressRankUF(int n) {
        this.n = n;
        this.parentArr = new int[n];
        this.rankArr = new int[n];
        for (int i = 0; i < parentArr.length; i++) {
            parentArr[i] = i;
            rankArr[i] = 0;
        }
    }

    int findRecurse(int i) {
        if (i == parentArr[i]) {
            return i;
        }
        parentArr[i] = findRecurse(parentArr[i]);
        return parentArr[i];
    }

    int findTraverse(int i) {
        while (parentArr[i] != i) {
            // 当前节点的父直接指向父的父
            parentArr[i] = parentArr[parentArr[i]];
            i = parentArr[i];
        }
        return i;
    }

    boolean isConnected(int p, int q) {
        if (p == q) {
            return true;
        }
        return findRecurse(p) == findRecurse(q);
    }

    void union(int p, int q) {
        int pRoot = findRecurse(p);
        int qRoot = findRecurse(q);
        if (pRoot == qRoot) {
            return;
        }
        if (rankArr[pRoot] > rankArr[qRoot]) {
            parentArr[qRoot] = pRoot;
        } else if (rankArr[pRoot] < rankArr[qRoot]) {
            parentArr[pRoot] = qRoot;
        } else {
            parentArr[pRoot] = qRoot;
            // 树高+1
            rankArr[qRoot] += 1;
        }
    }
}

看看我们100000数据量下的测试效果：

1
2
3
4
5

QuickFindUFTest 运行 100000次，耗时：3468ms
QuickUFTest 运行 100000次，耗时：12501ms
SizeUFTest 运行 100000次，耗时：25ms
RankUFTest 运行 100000次，耗时：24ms
CompressRankUFTest 运行 100000次，耗时：21ms

小结

基于数组我们实现了基本的并查集，并逐步优化了每个版本中的缺陷：

版本 缺陷 优化
QuickFindUF union操作复杂度O(n)
QuickUF union可能将较高的树合并到较低的树上，带来边缘情况下的性能退化 以树根组织数据，理论上提高了union的时间效率
SizeUF 通过元素数判断树高是不准确的，依然有QuickUF中的问题 判断树中元素数来决定合并时的策略，一定程度上防止了矮树合并到高树上
RankUF 树高未进行优化 通过树高判断合并策略，比Size的策略更准确
CompressRankUF 无 查找时压缩树高

一方面我们经过了理论上的分析、优化，一方面也需要做好工程使用下的压测，部分时间复杂度分析在极端情况下并不完全准确反映性能表现。

以上即我今天对并查集的实现、优化过程。

Ref