在看算法导论的并查集部分（p329）的时候发现里面提到“通过引入两种启发式策略（按秩合并和路径压缩），我们能得到一个渐近最优的不相交集合数据结构”。这里的路径压缩比较常见，但是按秩合并见的较少，理解起来也不那么容易。

按秩合并

按秩合并就是让具有较少结点的树的根指向具有较多结点的树的根，这里算法导论并没有简单粗暴的直接记录结点数量，而是采用了对每个结点维护一个秩的方法，秩表示该结点高度的一个上界。

原文中具体的描述如下：

实现

按秩合并的具体算法步骤如下：

(1)初始化一个数组，记录每个结点的秩，初始都为0

(2)当进行union操作时，需要比较该边两个结点的最终父节点（即树根）的秩：

A. 如果两个根的秩相同，任意选择一个根作为父节点，并且让该父节点的秩加1

B.如果秩不同，将秩小的根的父节点设置为秩大的根，但是秩不用进行任何修改

具体的伪代码如下：

路径压缩

路径压缩比较常见，就是在FIND过程中把途经的点的直接父节点都设置为最终父节点（根）。

实现

路径压缩的实现可以使用非递归、递归两种，递归写法更简练，用的比较多。

启发式策略的效率提升

根据算法导论所说，如果单独使用按秩合并、路径压缩其中的一种，都能一定程度改善并查集的效率，但是两种方法一起使用可以让效率达到极致。

同时使用按秩合并、路径压缩的最坏情况为O( m a(n) )，m是总的操作数（包括makeset，union，find），n是结点数。

a(n)是一个增长非常慢的函数，任何情况下都小于等于4，因此可以认为总的时间复杂度是和m成线性关系，具体证明见算法导论。