按等級改進聯合

另一種通常使用的啟發式方法，而不是按大小聯合，是按級別啟發式聯合

它的基本思想是我們實際上並不需要儲存集合的確切大小，大小的近似值（在這種情況下：大致是集合大小的對數）足以達到與大小相同的速度。

為此，我們引入了集合等級的概念，其給出如下：

• 單例排名 0
• 如果合併了具有不等等級的兩個集合，則具有較大等級的集合變為父集合而等級保持不變。
• 如果合併了兩組相等的等級，則其中一組成為另一組的父級（選擇可以是任意的），其等級遞增。

按等級聯合的一個優點是空間使用：隨著最大等級大致增加 ，對於所有實際輸入大小，等級可以儲存在單個位元組中（因為 n < 2^255）。

按等級簡單實現並集可能如下所示：

private:
    ...
    std::vector<unsigned char> rank;

public:
    union_find(size_t n) : parent(n), rank(n, 0) { ... }

    ...

    void merge(size_t i, size_t j) {
        size_t pi = find(i);
        size_t pj = find(j);
        if (pi == pj) {
            return;
        }
        if (rank[pi] < rank[pj]) {
            // link the smaller group to the larger one
            parent[pi] = pj;
        } else if (rank[pi] > rank[pj]) {
            // link the smaller group to the larger one
            parent[pj] = pi;
        } else {
            // equal rank: link arbitrarily and increase rank
            parent[pj] = pi;
            ++rank[pi];
        }
    }