data-structures Améliorations: Union par taille


Exemple

Dans notre implémentation actuelle de la merge , nous choisissons toujours le jeu de gauche comme étant l’enfant du jeu correct, sans tenir compte de la taille des jeux. Sans cette restriction, les chemins d'accès (sans compression de chemin ) d'un élément à son représentant pourraient être assez longs, ce qui entraînerait des temps d'exécution importants sur les appels de find .

Une autre amélioration courante est l'heuristique union by size , qui fait exactement ce qu'elle dit: lors de la fusion de deux ensembles, nous définissons toujours le plus grand ensemble comme étant le parent du plus petit ensemble, conduisant ainsi à une longueur de chemin d'au plus log n pas:

Nous stockons un membre supplémentaire std::vector<size_t> size dans notre classe qui est initialisé à 1 pour chaque élément. Lors de la fusion de deux ensembles, le plus grand ensemble devient le parent du plus petit ensemble et nous résumons les deux tailles:

private:
    ...
    std::vector<size_t> size;

public:
    union_find(size_t n) : parent(n), size(n, 1) { ... }

    ...

    void merge(size_t i, size_t j) {
        size_t pi = find(i);
        size_t pj = find(j);
        if (pi == pj) {            // If the elements are in the same set: 
            return;                // do nothing
        }
        if (size[pi] > size[pj]) { // Swap representatives such that pj
            std::swap(pi, pj);     // represents the larger set
        }
        parent[pi] = pj;           // attach the smaller set to the larger one
        size[pj] += size[pi];      // update the size of the larger set
    }