高级数据结构

1.并查集合

基本结构

大部分资料参考Awen同学和左同学，在这里表示感谢
并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（union-find algorithm）定义了两个用于此数据结构的操作：

isSameSet(find): 它可以被用来确定两个元素是否属于同一子集。
union: 将两个子集合并成同一个集合。

首先并查集本身是一个结构，我们在构造它的时候需要将所有要操作的数据扔进去，初始时每个数据自成一个结点，且每个结点都有一个父指针（初始时指向自己）。

初始化

初始时并查集中的每个结点都算是一个子集，我们可以对任意两个元素进行合并操作。值得注意的是，union(nodeA,nodeB)并不是单单只将结点nodeA和nodeB合并成一个集合，而是将nodeA所在的集合和nodeB所在的集合合并成一个新的子集：

图片说明

那么合并两个集合的逻辑是什么呢？首先要介绍一下父结点（代表节点）这个概念：找一结点所在集合的代表结点就是找这个集合中父指针指向自己的结点（并查集初始化时，每个结点都是各自集合的代表结点）。那么合并两个集合就是将结点个数较少的那个集合的代表结点指向另一个集合的代表结点：

图片说明

还有一个isSameSet(find)操作：查找两个结点是否所属同一个集合。我们只需判断两个结点所在集合的代表结点是否是同一个就可以了：

图片说明

通过观察发现，union操作和isSameSet都会有一个找到当前节点的父节点的过程，把它单独抽象成一个findFather的操作。在找一个结点的父节点时，会不停地向上找父指针，直到父节点指向自己的结点，利用一个容器收集沿途的节点，最后将沿途路过的结点的父指针改为直接指向代表结点：

图片说明

并查集合结构在样本量为N，操作频繁的前提下，也就是isSameSet和union的操作次数逼近O(N)或超过O(N)时，可认为它们是O(1)的时间复杂度。这得益于两点:

小集合挂在大集合，一次改动
在向上找父节点的过程中，沿途链表扁平化，树的高度维持在1

代码实现

在代码实现中，节点可以选择原本类型，也可以选择包装类，但在实际做题过程中都是原本类型。

// 样本进来会包一层，叫做元素
public static class Element<V> {
    public V value;

    public Element(V value) {
        this.value = value;
    }
}

定义并查集类，定义isSameSet，findFather和union函数:

public static class UnionFindSet{
    // 记录每个节点的父节点，也就是头节点
    public HashMap<Integer, Integer> fatherMap;
    // 记录每个头节点的所挂节点的总个数
    public HashMap<Integer, Integer> sizeMap;

    // 初始化并查集合
    public UnionFindSet(int N){
        fatherMap = new HashMap<Integer, Integer>();
        sizeMap = new HashMap<Integer, Integer>();
        for (int i=0; i<N; i++){
            fatherMap.put(i, i);
            sizeMap.put(i ,1);
        }
    }

    // 找到给定的节点的父节点
    public int findFather(int node){
        // 把向上找的过程中，沿途的点都放在path里
        Deque<Integer> stack = new ArrayDeque<>();
        while (node != fatherMap.get(node)){
            stack.push(node);
            node = fatherMap.get(node);
        }
        // 沿途节点，更改父亲节点
        while (!stack.isEmpty()){
            fatherMap.put(stack.pop(), node);
        }
        return node;
    }
    // 判断两个节点是否是一个集合
    public boolean isSameSet(int a, int b){
        return findFather(a) == findFather(b);
    }
    // 合并给定的两个节点
    public void union(int a, int b){
        int aF = findFather(a);
        int bF = findFather(b);
        // 不在一个集合，需要合并
        if (aF != bF){
            // 小节点挂在大节点上
            int big = sizeMap.get(aF) >= sizeMap.get(bF) ? aF : bF;
            int small = big == aF ? bF : aF;
            // 修改small的节点，挂在big上
            fatherMap.put(small, big);
            // 接受两个链表的和
            sizeMap.put(big, sizeMap.get(big) + sizeMap.get(small));
            sizeMap.remove(small);
        }
    }

    // 查询最后父节点的数目，也就是合并后，不相通的集合数量
    public int getNum(){
        return sizeMap.size();
    }

    public static void main(String[] args) {
        int n = 初始节点数量;
        // 在结构体中，每个节点都会先指向自己
        UnionFindSet unionFindSet = new UnionFindSet(n);
    }
}