algorithm 基于不交集的最佳实现

示例

我们可以做两件事来改进简单和次优不相交集子算法：

1. 路径压缩启发式：findSet不需要处理高度大于的树2。如果最终迭代了这样的树，它可以将较低的节点直接链接到根，从而优化将来的遍历。

   subalgo findSet(v: a node):
       ifv.parent!= v
          v.parent= findSet(v.parent)
       return v.parent
   

2. 基于高度的合并启发式：对于每个节点，存储其子树的高度。合并时，将较高的树作为较小树的父树，这样就不会增加任何人的身高。

   subalgo unionSet(u, v: nodes):
       vRoot = findSet(v)
       uRoot = findSet(u)
       if vRoot == uRoot:
           return
       ifvRoot.height< uRoot.height:
          vRoot.parent= uRoot
       else ifvRoot.height> uRoot.height:
          uRoot.parent= vRoot
       else:
          uRoot.parent= vRoot
          uRoot.height= uRoot.height+ 1
   

这会导致每次操作都花费时间，而这是快速增长的阿克曼函数的逆函数，因此增长非常缓慢，可以考虑用于实际目的。O(alpha(n))alphaO(1)

由于初始排序，因此构成了整个Kruskal的算法。O(m log m + m) = O(m log m)

注意

路径压缩可能会降低树的高度，因此在联合操作期间比较树的高度可能不是一件容易的事。因此，为了避免存储和计算树的高度的复杂性，可以随机选择生成的父级：

    subalgo unionSet(u, v: nodes):
        vRoot = findSet(v)
        uRoot = findSet(u)

        if vRoot == uRoot:
            return
        if random() % 2 == 0:
           vRoot.parent= uRoot
        else:
           uRoot.parent= vRoot

在实践中，这种随机算法与用于findSet操作的路径压缩一起将产生可比的性能，但实现起来要简单得多。