按等级改进联合

另一种通常使用的启发式方法，而不是按大小联合，是按级别启发式联合

它的基本思想是我们实际上并不需要存储集合的确切大小，大小的近似值（在这种情况下：大致是集合大小的对数）足以达到与大小相同的速度。

为此，我们引入了集合等级的概念，其给出如下：

• 单例排名 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];
        }
    }