基于最佳脱节集的实现

Created: November-22, 2018

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

路径压缩启发式 ：findSet 不需要处理高度大于 2 的树。如果它最终迭代这样一棵树，它可以将较低的节点直接链接到根，优化未来的遍历;
```
subalgo findSet(v: a node):
    if v.parent != v
        v.parent = findSet(v.parent)
    return v.parent
```

基于高度的合并启发式 ：对于每个节点，存储其子树的高度。合并时，让较高的树成为较小树的父母，从而不会增加任何人的身高。

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

    if vRoot == uRoot:
        return

    if vRoot.height < uRoot.height:
        vRoot.parent = uRoot
    else if vRoot.height > uRoot.height:
        uRoot.parent = vRoot
    else:
        uRoot.parent = vRoot
        uRoot.height =  uRoot.height + 1

这导致每次操作的时间为 3h，其中 alpha 是快速增长的 Ackermann 函数的倒数，因此它的生长非常缓慢，并且可以被认为是实际目的的 O(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 操作的路径压缩一起将产生可比较的性能，但实现起来要简单得多。