需求分析

• 假设有 N 个村庄, 有些村庄之间有连接的路，有些村庄之间没有连接的路
• 设计一个数据结构，能够快速执行两个操作
  • 查询两个村庄之间是否有连接的路
  • 连接两个村庄
• 数组 和 链表？
  • 使用N个数组(或者链表), 保存能连接的村庄
    • 查询时，遍历数组， 查看是否连接
      • 时间复杂度 O(N)
    • 连接时，把两个数组合并。
      • 时间复杂度 O(N)
• 平衡二叉树 ？
  • 显然，村庄没有大小关系, 平衡二叉树无法排序，所以不可用
• 集合 ？
  • 使用N个集合，保存能连接的村庄
    • 查询时，查看两个元素是否在一个set中
      • 看起来，是可以在 O(1) 的时间复杂度内查找到，但是如果一个集合中只有一个元素呢？ 就相当于查看N个数组
      • 所以其时间复杂度仍然是 O(N)
    • 连接时，把两个集合合并
  • 而且集合的底层，是哈希表 + 红黑树 + 链表.使用这么复杂的数据结构，来解决这个问题，有些杀鸡用牛刀的感觉。

并查集

概念

• 并查集能够办到 查询，连接 的均摊时间复杂度都是 O(alpha(N)) , alpha(n) < 5

• 并查集非常适合解决这类 连接 相关的问题

• 并查集也叫做不相交集合

• 有2个核心操作

  • 查找(Find) : 查找元素所在的集合(这里的集合并不是特指Set这种数据结构, 是指广义的数据结构)
  • 合并(Union) : 将两个元素所在的集合合并为一个集合

两种实现思路

比如有两个帮派合并, 帮派A合并进帮派B

Quick Find

• QuickFind就是，把帮派A中所有的小弟都认帮派B中的头目当老大

• 查找(Find) : 的时间复杂度 : O(1)

• 合并(uniol) : 的时间复杂度 : O(N)

Quick Union

• QuickUnion就是, 帮派A的头目认帮派B的头目当老大，这时帮派A所有小弟的老大也是帮派B的头目
• **查找(Find)**的时间复杂度: O(log N), 可以优化至 O(alpha(n)), alpha(n) < 5
• **合并(Union)**的时间复杂度: O(log N),可以优化至 O(alpha(n)), alpha(n) < 5

如何存储数据？

• 假设并查集处理的数据都是整型，那么可以用整型数组来存储数据

• 因此，并查集是可以用数组实现的树形结构(二叉堆, 优先级队列也是可以用数组实现的树形结构)

接口定义

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

    /**
     * 查找v所属的集合
     * @param v 查询元素
     * @return 所属集合
     * */
    public abstract int find(int v);

    /**
     * 合并v1, v2 两个并查集
     * */
    public abstract void union(int v1, int v2);

    /**
     * 两个元素是否在同一集合
     * */
    public boolean isSame(int v1, int v2){
        return find(v1) == find(v2);
    }

初始化

• 初始化时，每个元素各自数据一个蛋元素的集合

  

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

protected int[] parents;

public UnionFind(int capacity) {
    if (capacity < 0)
        throw new IllegalArgumentException("capacity mast >= 1");
    parents = new int[capacity];
    for (int i = 0; i < parents.length; i++) {
        parents[i] = i;
    }
}

QuickFind

• Quick Find 的 union(v1, v2) : 让v1 所在集合的所有元素都指向v2的根节点

  

  

QuickFind-Union

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

/**
 * 将v1所在集合的所有元素，都嫁接到v2的父节点上
 */
@Override
public void union(int v1, int v2) {

    int p1 = find(v1);
    int p2 = find(v2);
    if (p1 == p2) return;

    for (int i = 0; i < parents.length; i++) {
        if (parents[i] == p1)
            parents[i] = p2;
    }
}

• 将 v1 所在集合的所有元素，都嫁接到v2的父节点上
• 时间复杂度 : O(N)

QuickFind-Find

1
2
3
4
5
6
7
8

/**
 * 父节点就是根节点
 */
@Override
public int find(int v) {
    rangeCheck(v);
    return parents[v];
}

• 因为在 Union 操作中， 被合并的集合中所有的父节点都指向合并后的根节点，所以 父节点 就是 根节点
• 时间复杂度 ： O(1)

QuickUnion - Union

• QuickUnion 的 union(v1, v2) : 让v1的根节点指向v2的根节点(想想例子，帮派A中的所有小弟都认帮派B的头目当老大)

  

  

QuickUnion-Union

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

/**
 * 将v1的根节点嫁接到v2的根节点上
 */
@Override
public void union(int v1, int v2) {
    int p1 = find(v1);
    int p2 = find(v2);
    if (p1 == p2) return;

    parents[p1] = parents[p2];
}

• 时间复杂度 : O(log N) 找根节点的过程花费时间logN

QuickUnion-Find

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

/**
 * 通过parent链条不断地向上找，直到找到根节点
 */
@Override
public int find(int v) {
    rangeCheck(v);
    while (v != parents[v]){
        v = parents[v];
    }
    return v;
}

时间复杂度 : O(log N)

QuickUnion 的 优化

• 在 Union 的过程中, 可能会出现树不平衡的情况，甚至退化成链表

  

• 有两种常见的优化方案

  • 基于size的优化 : 元素少的树 嫁接到 元素多的树
  • 基于rank的优化: 矮的树 嫁接到 高的树

基于 size 的优化

• 额外使用 sizes 数组 保存各个元素集合的数量
• 当 合并时, 把元素少的 合并到 元素多的中

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

@Override
public void union(int v1, int v2) {
    int p1 = find(v1);
    int p2 = find(v2);
    if (p1 == p2) return;

    if (sizes[p1] < sizes[p2]){
        // p1 元素数量少
        parents[p1] = p2;
        sizes[p2] += sizes[p1];
    }else {
        // p1 元素数量多
        parents[p2] = p1;
        sizes[p1] += sizes[p2];
    }
}

• 基于size的优化，会一定程度上避免树不平衡的问题
• 但是也可能存在树不平衡的问题

基于 rank 的优化

• 使用 ranks 数组保存，每个元素的树高
• 合并时，把树高低的合并到树高高的中去
  • 当树高不一致时，直接合并即可，合并完毕，树高不会改变
  • 当树高一致时，随便合并一个， 合并者的树高 + 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

@Override
public void union(int v1, int v2) {
    int p1 = find(v1);
    int p2 = find(v2);
    if (p1 == p2) return;

    if (ranks[p1] < ranks[p2]){
        // p1树高比较矮
        parents[p1] = p2;
    }else if (ranks[p1] > ranks[p2]){
        // p1树高高
        parents[p2] = p1;
    }else {
        // 两棵树高相等
        parents[p1] = p2;
        ranks[p2] += 1;
    }
}

路径压缩(Path Compression)

• 虽然有了基于 rank 的优化，树会相对平衡一点

• 但是随着 union 次数的增多，树的高度依然会越来越高

  • 导致find操作变慢，尤其是底层节点(因为find是不断向上找到根节点)

• 什么是路径压缩？

  • 在find时，使路径上的所有节点都指向根节点，从而降低树的高度

  

  1 2 3 4 5 6 7 8 9

  @Override public int find(int v) { rangeCheck(v); if (parents[v] != v){ parents[v] = find(parents[v]); } return parents[v]; }

  • 路径压缩使路径上的所有节点都指向根节点，所以实现成本稍高

状态分裂(Path Spliting)

• 使路径上每个节点都指向起祖父节点

  

  1 2 3 4 5 6 7 8 9 10

  @Override public int find(int v) { rangeCheck(v); while (v != parents[v]){ int p = parents[v]; parents[v] = parents[parents[v]]; v = p; } return v; }

路径减半 (Path Halving)

• 路径减半： 使路径上每隔一个节点就指向起祖父节点

  

  1 2 3 4 5 6 7 8 9 10

  @Override public int find(int v) { rangeCheck(v); while (v != parents[v]){ parents[v] = parents[parents[v]]; v = parents[v]; } return v; }