data-structures Améliorations: Union par rang


Exemple

Une autre heuristique couramment utilisée à la place de l'union par la taille est l'heuristique union par rang

Son idée de base est que nous n'avons pas besoin de stocker la taille exacte des ensembles, une approximation de la taille (dans ce cas: approximativement le logarithme de la taille de l'ensemble) suffit pour atteindre la même vitesse que l'union par taille.

Pour cela, nous introduisons la notion de rang d'un ensemble, qui est donnée comme suit:

  • Singletons ont le rang 0
  • Si deux ensembles de rangs inégaux sont fusionnés, l'ensemble ayant le plus grand rang devient le parent tandis que le rang reste inchangé.
  • Si deux ensembles de même rang sont fusionnés, l'un d'eux devient le parent de l'autre (le choix peut être arbitraire), son rang est incrémenté.

L'un des avantages de l' union par rang est l'utilisation de l'espace: à mesure que le rang maximal augmente log n , pour toutes les tailles d'entrée réalistes, le classement peut être stocké dans un seul octet (puisque n < 2^255 ).

Une simple implémentation de l'union par rang pourrait ressembler à ceci:

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];
        }
    }