基於最佳脫節集的實現

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 操作的路徑壓縮一起將產生可比較的效能，但實現起來要簡單得多。