1.Introduce
并查集是一种数据结构，能够很不便地判断两个元素是否属于同一汇合，对于并查集的演示demo，能够参考slides或其余路径，本次课Josh老师循序渐进地从并查集的数据结构抉择开始一步步优化，最终使并查集失去绝对较好的性能体现。简略来讲，并查集须要领有两个性能:
- isConnected()：判断两个元素之间是否相连接(属于同一汇合)
- Connect():连贯两个元素，在连贯之前应该判断元素是否已相连
因而咱们创立一个DisjointSets接口，并在继承它的子类里实现上述两种办法：
public interface DisjointSets { /** Connects two items P and Q. */ void connect(int p, int q); /** Checks to see if two items are connected. */ boolean isConnected(int p, int q);}2.ListOfSetsDS
首先的问题是:如何去示意各个不相交汇合,一说到汇合，很容易想到应用Java内置的Set，那么就会有\(Set_{0},Set_{1},Set_{2}......\)
因而能够应用List<Set<Integer>>的模式示意，这里假如元素类型是Integer，其实视频里说，这是Berkeley学生的想法，我也没想到，（= =）这种数据结构看起来比较复杂，Josh说实现起来也很简单，然而我感觉不算简单，说说我的想法。
比方想要把\(Set_{0}中的元素1和Set_{1}中的元素2\)相连，思考:
IsConnected()：\(调用Set_{0}.contains()即可\)，应用HastSet的话，工夫复杂度应该低于\(\Theta(N)\)
Connect()：\(调用Set_{0}.add()即可，假如Set_{1}的大小为M，则工夫复杂度为\Theta(M)\)
然而只是最开始还算比拟快，如果把一个List中的Set全副两两合并，越到前面执行单次合并的工夫复杂度就越高。
Performance Summary
3.QuickFindDS(疾速查找)
经验了下面的想法之后，咱们的想法是:并查集的底层数据结构应该是数组。且为了实现疾速查找的性能，须要一些改变
具体实现为:
首先对于各个不相交的汇合，给每一个汇合一个id，数组下标代表单个元素的值，数组外面存值为id，对于属于同一个汇合内的元素，则存储雷同的id值,图例:
如图,假如{0,1,4,2}属于汇合4，则在数组下标为0 , 1 , 2 , 4处的值都贮存为4，那么当初考虑一下并查集的两个操作:
IsConnected()：i和j是否属于同一汇合，只需比拟a[i]与a[j]的值，工夫复杂度为O(1)
Connect()：遍历数组，如果连贯(2,3)以上图为例，只需将a[0],a[1],a[2],a[4]改为5，也就是将汇合1中全副的元素的汇合id都改为汇合2的汇合id，工夫复杂度为O(N)
代码实现
public class QuickFindDS implements DisjointSets { private int[] id; public QuickFindDS(int N) { id = new int[N]; for (int i = 0; i < N; i++) id[i] = i; } } public boolean isConnected(int p, int q) { return id[p] == id[q]; } public void connect(int p, int q) { int pid = id[p]; int qid = id[q]; for (int i = 0; i < id.length; i++) { if (id[i] == pid) { id[i] = qid; } }...Performance Summary
4.Quick Union(疾速合并)
下面咱们实现了并查集的疾速查找，判断两个元素是否属于同一汇合的效率达到O(1),然而对于合并操作其效率为O(N)，因为须要遍历整个数组，把属于同一个汇合中的元素对应的原来的汇合id更改为新的。
那么如何放慢合并操作的效率呢?在原来的根底上，数组外面的存储的值不再是汇合的id，而是各个元素的父节点的值。例如:
4的父节点是0，2的父节点是1，1的父节点是0，5的父节点是3，0和6的父节点是其自身，那么在数组中，下标代表元素本身的值，而数组外面的存值存储父节点的值，父节点是本身的存储为-1，造成如下的树形构造(孩子双亲表示法):
那么当初如果想要连贯(5,2),只须要寻找5的根节点--3和2的根节点--0,而后将3作为0的儿子连贯即可，将a[3]=0
如此一来，合并操作效率变为了O(1)，只需一步操作，更改汇合的根节点对应值即可。
然而事实上，查找的效率不再是O(1)，假如咱们判断两个元素a,b是否相连:
IsConnected():查找a的根，查找b的根，判断是否相等，工夫复杂度为O(H)，其中H为树的高度，最坏状况下，如果树的形态是这样的:
那么查找的工夫复杂度是O(N)
因为每次进行合并前均须要判断是否曾经相连操作，因而，只管合并只须要一步，然而总的工夫复杂度依然是O(N)
代码实现
public class QuickUnionDS implements DisjointSets { private int[] parent; public QuickUnionDS(int N) { parent = new int[N]; for (int i = 0; i < N; i++) { parent[i] = -1; } } private int find(int p) { int r = p; while (parent[r] >= 0) { r = parent[r]; } return r; } public boolean isConnected(int p, int q) { return find(p) == find(q); } public void connect(int p, int q) { int i = find(p); int j = find(q); parent[i] = j;}Performance Summary
5.改良1 Weighted Quick Union(加权疾速合并)
下面咱们看到，要想查找的效率为O(1)，则合并的步骤须要O(N)，要想一步即实现合并，那么查找须要O(N)，仿佛二者是不可兼得的，而且对于孩子双亲表示法，树越高那么查找的性能就越差，因为查找的过程是相当于爬树，如何防止合并过程中树变得越来越高也是一个重要的优化过程。
对于两个汇合的合并，咱们很容易想到，通过比拟两棵树的高度，将矮树的根 作为 高树的根的子树，这样能够防止树高度的减少，均匀查找效率为O(logN)
然而换一种思路:
一棵树的所有结点数量定义为该树的权(Weight)，咱们总是将小树的根连贯到大树的根上。
因而当初咱们要想方法追踪权值，可选的办法有:
- 1.根节点在数组中的值不再存储-1，而是存储 负权值
- 2.再开一个size数组，专门存储对应的结点的权值
两种办法都能够，那么让咱们来考虑一下按权疾速合并的工夫复杂度:
假如当初只有一个元素0：
树的高度为0，元素个数1
当初合并0和1:
树的高度为1，元素个数2
要想将树的高度从1变为2，只减少1个元素是不行的，假如合并1和2，依照按权合并的规定，将小树2的根作为大树0的根的孩子:
树的高度仍然为1，因而3个元素不可能使树的高度为2，要想让树的高度+1，须要四个元素:
同理可类推，要想树的高度为3，须要8个元素:
要想树的高度为4，须要16个元素:
察看可知最坏状况下树的高度为\(log_{2}N\)，因而工夫复杂度为\(\Theta(N)\)
那么其实按权合并和按高度合并的工夫复杂度都是\(\Theta(N)\)，为何抉择按权合并呢?
是因为在雷同的\(\Theta(N)\)下，按权合并的代码实现更简略
Performance Summary
6.改良2 Path Compression(门路压缩)
考虑一下，假如咱们要判断15和10是否连贯，须要查找:
15-->11-->5-->1
再查找10-->3-->0
须要logN的工夫进行查找，再合并，假如在查找的过程中，将沿途通过的结点的父结点全副都改成根节点0，让他们间接隶属于根节点:
那么下次再判断15和10是否相连时，只须要O(1)的操作，这就是门路压缩。
代码:
int find(int x){ if(fa[x] < 0) return x; else{ fa[x] = find(fa[x]); return fa[x]; }}这里说门路压缩的效率是严格来说是\(O(\alpha(N),其中,\alpha(N)是反阿克曼函数，非常靠近常数\)
proved by Tarjan here at UC Berkeley in 1975
其增长与N的关系为:
Performance Summary
假如对N个元素的并查集进行M次操作，工夫复杂度表:
文章举荐
门路压缩
并查集