data-structures
Estructura de datos de búsqueda de la unión

Introducción

Teoría

Las estructuras de datos de búsqueda de unión proporcionan las siguientes operaciones:

• make_sets(n) inicializa una estructura de datos de búsqueda de unión con n singletons
• find(i) devuelve un representante para el conjunto del elemento i
• union(i,j) fusiona los conjuntos que contienen i y j

Nosotros representamos a nuestra partición de los elementos de 0 a n - 1 mediante el almacenamiento de un elemento padre parent[i] para cada elemento i que finalmente conduce a un representante del conjunto que contiene i .
Si un elemento en sí es un representante, es su propio padre, es decir, el parent[i] == i .

Por lo tanto, si comenzamos con conjuntos singleton, cada elemento es su propio representante:

Podemos encontrar el representante para un conjunto dado simplemente siguiendo estos punteros principales.

Veamos ahora cómo podemos unir conjuntos:
Si queremos fusionar los elementos 0 y 1 y los elementos 2 y 3, podemos hacer esto configurando el padre de 0 a 1 y configurando el padre de 2 a 3:

En este caso simple, solo se deben cambiar los elementos del puntero principal.
Sin embargo, si queremos combinar conjuntos más grandes, siempre debemos cambiar el puntero principal del representante del conjunto que se fusionará en otro conjunto: después de la combinación (0,3) , hemos establecido el principal del representante del conjunto Contiene 0 al representante del conjunto que contiene 3.

Para hacer el ejemplo un poco más interesante, ahora también fusionamos (4,5), (5,6) y (3,4) :

La última noción que quiero introducir es la compresión de ruta :
Si queremos encontrar el representante de un conjunto, es posible que tengamos que seguir varios indicadores principales antes de llegar al representante. Podríamos hacer esto más fácil almacenando el representante para cada conjunto directamente en su nodo principal. Perdemos el orden en el que fusionamos los elementos, pero potencialmente podemos tener una gran ganancia en tiempo de ejecución. En nuestro caso, las únicas rutas que no están comprimidas son las rutas de 0, 4 y 5 a 3:

Implementacion basica

La implementación más básica de una estructura de datos de búsqueda de unión consiste en una matriz parent almacena un elemento principal para cada elemento de la estructura. Seguir estos 'punteros' primarios para un elemento i nos lleva al representante j = find(i) del conjunto que contiene i , donde retiene el parent[j] = j .

using std::size_t;

class union_find {
private:
    std::vector<size_t> parent;  // Parent for every node

public:
    union_find(size_t n) : parent(n) {
        for (size_t i = 0; i < n; ++i)
            parent[i] = i;      // Every element is its own representative
    }

    size_t find(size_t i) const {
        if (parent[i] == i)     // If we already have a representative
            return i;           // return it
        return find(parent[i]); // otherwise return the parent's representative
    }

    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 not in the same set: 
            parent[pi] = pj;   // Join the sets by marking pj as pi's parent
        }
    }
};

Mejoras: Compresión de ruta.

Si hacemos muchas operaciones de merge en una estructura de datos de búsqueda de unión, las rutas representadas por los punteros parent pueden ser bastante largas. La compresión de ruta , como ya se describió en la parte de teoría, es una forma simple de mitigar este problema.

Podríamos intentar hacer una compresión de ruta en toda la estructura de datos después de cada operación de fusión k -ésima o algo similar, pero tal operación podría tener un tiempo de ejecución bastante grande.

Por lo tanto, la compresión de ruta se usa principalmente en una pequeña parte de la estructura, especialmente en la ruta por la que caminamos para encontrar el representante de un conjunto. Esto se puede hacer almacenando el resultado de la operación de find después de cada subcall recursiva:

size_t find(size_t i) const {
    if (parent[i] == i)          // If we already have a representative
        return i;                // return it
    parent[i] = find(parent[i]); // path-compress on the way to the representative
    return parent[i];            // and return it
}

Mejoras: Unión por tamaño.

En nuestra implementación actual de merge , siempre elegimos que el conjunto izquierdo sea el hijo del conjunto correcto, sin tener en cuenta el tamaño de los conjuntos. Sin esta restricción, las rutas (sin compresión de ruta ) de un elemento a su representante pueden ser bastante largas, lo que lleva a grandes tiempos de ejecución en las llamadas de find .

Otra mejora común es la unión por tamaño heurístico, que hace exactamente lo que dice: cuando se combinan dos conjuntos, siempre establecemos que el conjunto más grande es el padre del conjunto más pequeño, lo que lleva a una longitud de ruta de como máximo pasos:

Almacenamos un std::vector<size_t> size adicional de miembro std::vector<size_t> size en nuestra clase que se inicializa a 1 para cada elemento. Al fusionar dos conjuntos, el conjunto más grande se convierte en el padre del conjunto más pequeño y resumimos los dos tamaños:

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
    }

Mejoras: Unión por rango.

Otra heurística utilizada comúnmente en lugar de unión por tamaño es la unión por rango heurístico

Su idea básica es que en realidad no necesitamos almacenar el tamaño exacto de los conjuntos, una aproximación del tamaño (en este caso: aproximadamente el logaritmo del tamaño del conjunto) es suficiente para lograr la misma velocidad que la unión por tamaño.

Para esto, introducimos la noción del rango de un conjunto, que se da a continuación:

• Singletons tiene rango 0
• Si dos conjuntos con rango desigual se combinan, el conjunto con rango más alto se convierte en el padre mientras que el rango se mantiene sin cambios.
• Si se combinan dos conjuntos de igual rango, uno de ellos se convierte en el padre del otro (la elección puede ser arbitraria), su rango se incrementa.

Una ventaja de la unión por rango es el uso del espacio: a medida que el rango máximo aumenta aproximadamente como Para todos los tamaños de entrada realistas, el rango se puede almacenar en un solo byte (ya que n < 2^255 ).

Una implementación simple de unión por rango podría verse así:

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

Mejora final: Unión por rango con almacenamiento fuera de los límites

Mientras que en combinación con la compresión de ruta, union by rank casi logra operaciones de tiempo constante en estructuras de datos de union-find, hay un truco final que nos permite deshacernos del almacenamiento de rank almacenando el rango en las entradas fuera de los límites de la matriz parent . Se basa en las siguientes observaciones:

• En realidad, solo necesitamos almacenar el rango para los representantes , no para otros elementos. Para estos representantes, no necesitamos almacenar un parent .
• Hasta ahora, el parent[i] tiene un size - 1 máximo de size - 1 , es decir, no se utilizan los valores más grandes.
• Todos los rangos están a lo sumo .

Esto nos lleva al siguiente enfoque:

• En lugar de la condición parent[i] == i , ahora identificamos representantes por
  parent[i] >= size
• Utilizamos estos valores fuera de límites para almacenar los rangos del conjunto, es decir, el conjunto con el representante i tiene rango parent[i] - size
• Por lo tanto, inicializamos la matriz principal con parent[i] = size lugar de parent[i] = i , es decir, cada conjunto es su propio representante con rango 0.

Como solo compensamos los valores de rango por size , simplemente podemos reemplazar el vector de rank por el vector parent en la implementación de la merge y solo necesitamos intercambiar la condición que identifica a los representantes en find :

Implementación terminada usando unión por rango y compresión de ruta:

using std::size_t;

class union_find {
private:
    std::vector<size_t> parent;

public:
    union_find(size_t n) : parent(n, n) {} // initialize with parent[i] = n

    size_t find(size_t i) const {
        if (parent[i] >= parent.size()) // If we already have a representative
            return i;                   // return it
        return find(parent[i]);         // otherwise return the parent's repr.
    }

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