\(9.3\)快速合并

1.根节点的引入

  假如我们想让connect操作快一些，由于先前用\(id[x]\)代指所属集合的操作仍是通过遍历序列实现的，时间复杂度为线性，我们希望用一个元素代指整个集合，这样合并操作只需要合并两个元素即可。

  对序列中的每个元素，我们给它分派(\(assign\))一个值，这个值是它的父亲(\(parent\))的索引；如果某个元素没有索引，那么它就是根节点，我们给它分派一个负数的值。下面的图示展示了{0, 1, 2, 4}, {3, 5}, {6}的对应表示：

  为了实现快速合并，我们引入一个辅助函数find(int item)，它返回某个元素对应的根节点。

2.connect(x, y)

  为了合并两元素，我们找到两个元素对应的根节点，然后让其中一个根节点作为另一个的儿子(\(child\))。例如connect(5, 2)需要进行如下操作：

1. find(5) \(\rightarrow 3\)
2. find(2) \(\rightarrow 0\)
3. 设置parent[3] = 0

3.isConnected(x, y)

  如果两个元素同属一个集合，那么它们的根节点应该相同。只需检查find(x) == find(y)即可。

4.总结与代码实现

  看起来快速合并的运行时间比快速查询长！但是\(O(n)\)代表的是快速合并的上界。当我们的树比较平衡时，快速查询的时间复杂度会非常优秀。

public class QuickUnionDS implements DisjointSets {
    private int[] parent;

    public QuickUnionDS(int num) {
        parent = new int[num];
        for (int i = 0; i < num; i += 1) {
            parent[i] = -1;
        }
    }

    private int find(int p) {
        while(parent[p] >= 0) {
            p = parent[p];
        }
        return p;
    }

    @Override
    public void connect(int p, int q) {
        int i = find(p);
        int j = find(q);
        parent[i] = j;
    }

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