Heap aleatorizado

Un heap aleatorizado es un heap que, usando aleatorización, permite realizar todas las operaciones en tiempo logarítmico esperado.

Un min heap es un árbol binario en el que el valor de cada vértice es menor o igual que los valores de sus hijos. Así, el mínimo del árbol está siempre en el vértice raíz.

Un max heap se puede definir de forma similar: reemplazando menor por mayor.

Las operaciones por defecto de un heap son:

Agregar un valor
Extraer el mínimo
Quitar el mínimo
Mergear dos heaps (sin borrar duplicados)
Quitar un elemento arbitrario (si se conoce su posición en el árbol)

Un heap aleatorizado puede hacer todas estas operaciones en tiempo esperado $O(\log n)$ con una implementación muy simple.

Estructura de datos

Podemos describir de inmediato la estructura del heap binario:


struct Tree {
    int value;
    Tree * l = nullptr;
    Tree * r = nullptr;
};

En el vértice guardamos un valor. Además tenemos punteros a los hijos izquierdo y derecho, que apuntan a null si el hijo correspondiente no existe.

Operaciones

No es difícil ver que todas las operaciones se pueden reducir a una sola: mergear dos heaps en uno. En efecto, agregar un valor nuevo al heap es equivalente a mergear el heap con un heap que consiste de un solo vértice con ese valor. Encontrar un mínimo no requiere ninguna operación: el mínimo es simplemente el valor en la raíz. Quitar el mínimo es equivalente al resultado de mergear los hijos izquierdo y derecho del vértice raíz. Y quitar un elemento arbitrario es similar. Mergeamos los hijos del vértice y reemplazamos el vértice por el resultado del merge.

Así que en realidad solo hay que implementar la operación de mergear dos heaps. Todas las demás operaciones se reducen trivialmente a esta operación.

Sean dos heaps $T_1$ y $T_2$ . Está claro que la raíz de cada uno de estos heaps contiene su mínimo. Así que la raíz del heap resultante será el mínimo de estos dos valores. Comparamos ambos valores y usamos el más chico como nueva raíz. Ahora hay que combinar los hijos del vértice seleccionado con el heap restante. Para esto seleccionamos uno de los hijos y lo mergeamos con el heap restante. Así tenemos de nuevo la operación de mergear dos heaps. Tarde o temprano este proceso termina (el número de esos pasos está limitado por la suma de las alturas de los dos heaps).

Para lograr complejidad logarítmica en promedio, hay que especificar un método para elegir uno de los dos hijos de modo que la longitud promedio del camino sea logarítmica. No es difícil adivinar que tomaremos esta decisión al azar. Así, la implementación de la operación de merge es la siguiente:


Tree* merge(Tree* t1, Tree* t2) {
    if (!t1 || !t2)
        return t1 ? t1 : t2;
    if (t2->value < t1->value)
        swap(t1, t2);
    if (rand() & 1)
        swap(t1->l, t1->r);
    t1->l = merge(t1->l, t2);
    return t1;
}

Acá primero chequeamos si uno de los heaps está vacío; entonces no hay que hacer ninguna acción de merge. Si no, hacemos que el heap t1 sea el que tiene el valor más chico (intercambiando t1 y t2 si hace falta). Queremos mergear el hijo izquierdo de t1 con t2, por lo tanto intercambiamos al azar los hijos de t1, y después hacemos el merge.

Complejidad

Introducimos la variable aleatoria $h(T)$ que denotará la longitud del camino aleatorio de la raíz a la hoja (la longitud en número de aristas). Está claro que el algoritmo merge realiza $O(h(T_1) + h(T_2))$ pasos. Por lo tanto, para entender la complejidad de las operaciones, hay que mirar la variable aleatoria $h(T)$ .

Valor esperado

Asumimos que la esperanza $h(T)$ se puede acotar por arriba por el logaritmo del número de vértices en el heap:

$\mathbf{E} h(T) \le \log(n+1)$

Esto se puede demostrar fácilmente por inducción. Sean $L$ y $R$ los subárboles izquierdo y derecho de la raíz $T$ , y $n_L$ y $n_R$ el número de vértices en ellos ( $n = n_L + n_R + 1$ ).

Lo siguiente muestra el paso inductivo:

$\begin{aligned} E h (T) & = 1 + \frac{E h (L) + E h (R)}{2} \leq 1 + \frac{\log (n_{L} + 1) + \log (n_{R} + 1)}{2} \\ = 1 + \log \sqrt{(n_{L} + 1) (n_{R} + 1)} = \log 2 \sqrt{(n_{L} + 1) (n_{R} + 1)} \\ \leq \log \frac{2 ((n_{L} + 1) + (n_{R} + 1))}{2} = \log (n_{L} + n_{R} + 2) = \log (n + 1) \end{aligned}$

Exceder el valor esperado

Por supuesto todavía no estamos contentos. El valor esperado de $h(T)$ no dice nada sobre el peor caso. Todavía es posible que los caminos de la raíz a los vértices sean en promedio mucho mayores que $\log(n + 1)$ para un árbol específico.

Demostremos que la probabilidad de exceder el valor esperado es de hecho muy chica:

${\cal P}(h(T) > (c+1) \log n) < \frac{1}{n^c}$

para cualquier constante positiva $c$ .

Acá denotamos por $P$ el conjunto de caminos de la raíz del heap a las hojas cuya longitud excede $(c+1) \log n$ . Nótese que para cualquier camino $p$ de longitud $|p|$ la probabilidad de que se elija como camino aleatorio es $2^{-|p|}$ . Por lo tanto obtenemos:

${\cal P}(h(T) > (c+1) \log n) = \sum_{p \in P} 2^{-|p|} < \sum_{p \in P} 2^{-(c+1) \log n} = |P| n^{-(c+1)} \le n^{-c}$

Complejidad del algoritmo

Así el algoritmo merge, y por lo tanto todas las demás operaciones expresadas con él, se pueden realizar en $O(\log n)$ en promedio.

Además, para cualquier constante positiva $\epsilon$ hay una constante positiva $c$ tal que la probabilidad de que la operación requiera más de $c \log n$ pasos es menor que $n^{-\epsilon}$ (en cierto sentido esto describe el comportamiento de peor caso del algoritmo).