De todo el zoológico, esta estructura es quizás la más inusual. Al mismo tiempo, la elegante simplicidad del algoritmo coincide bastante con su sorprendente excentricidad.Al ordenar con un montón débil, siempre hay menos comparaciones e intercambios que con un montón normal. Entonces, sí, una pila débil es más fuerte que una pila normal.
Este artículo fue escrito con el apoyo de EDISON.
Nos dedicamos a la creación de software integrado , así como al desarrollo de aplicaciones y sitios web .
¡Nos encanta la teoría de los algoritmos! ;-)
Pila débil
Un montón normal es un árbol de clasificación en el que cualquier padre es mayor (o igual) que cualquiera de sus descendientes. En un montón débil, este requisito se debilita: cualquier padre es mayor que (o igual a) cualquier descendiente solo de su subárbol derecho. En el subárbol izquierdo, los descendientes pueden ser más pequeños y más grandes que el padre, ahí tienes tanta suerte.Este enfoque puede reducir significativamente el costo de mantener el conjunto de datos en un estado dinámico. Después de todo, es necesario garantizar el principio "un descendiente no es más que un padre", no para toda la estructura, sino solo para su mitad. Al mismo tiempo, un montón débil, que no es un árbol de clasificación al 100%, no es peor que un montón común y, en algunos aspectos, incluso mejor. Hice la mitad de la batalla: ¡camina con valentía!Como la raíz del montón, incluso una débil, necesita exactamente el elemento más grande, la raíz del subárbol izquierdo no.Minimizando el número de comparaciones
Un grupo débil nos dio un especialista en algoritmos y teoría de grafos Ronald D. Dutton en 1993. Una pila conceptualmente débil es más difícil de entender (pero es más probable que esta dificultad no sea en complejidad, sino en extravagancia, tienes que romper tus patrones de conciencia a través de la rodilla) que una pila normal, por lo que no ha recibido mucha distribución práctica. Sin embargo, cuando Dutton inventó esta estructura, no solo quería practicar abstracciones abstractas, sino que persiguió un objetivo completamente pragmático.Existe un límite inferior teórico para estimar el número mínimo de comparaciones (en aquellas clasificaciones en las que estas comparaciones son ampliamente utilizadas):log n ! = n log n - n / ln 2 + O (log n), donde 1 / ln 2 = 1.4426Al ordenar por un montón débil, el número de comparaciones se minimiza y está lo suficientemente cerca del límite inferior.Esto puede ser de importancia práctica si necesita organizar objetos cuya comparación es costosa, por ejemplo, si se trata de ordenar cadenas largas.Malabares descendientes
"Izquierda" y "derecha" en un montón débil es un fenómeno situacional. Un subárbol puede ser un descendiente izquierdo o derecho para su nodo padre; además, esta relación "izquierda / derecha" para el subárbol y el padre puede cambiar repetidamente de un valor al opuesto durante el proceso.Indicar para el padre que tiene su hijo correcto y quién es su hija izquierda no es simple, sino muy simple. Para hacer esto, necesita un mapa de bits adicional (que consta de solo valores 0/1) para los nodos que tienen descendientes.Recordemos cómo el índice i -ésimo elemento padre, definimos los índices de su descendiente izquierdo y derecho en una pila convencional (índices de la matriz medidos desde cero):descendiente izquierdo 2 × i + 1descendiente derecho 2 × i + 2En un montón débil, tenemos una cereza en el pastel: una raíz que solo tiene el subárbol correcto, por lo que ajustaremos estas fórmulas para los índices descendientes agregando un desplazamiento inverso a 1 posición:descendiente izquierdo: 2 × idescendiente derecho: 2 × i + 1y finalmente , necesitaba un mapa de bits adicional ( llámelo bIT ), en el que el elemento i -ésimo observado era si el intercambio se coloca entre sus subárboles izquierdo y derecho. Si el valor de un elemento es 0, entonces no hubo intercambio. Si el valor es 1, los hijos izquierdo y derecho van en el orden opuesto. Y las fórmulas en este caso son las siguientes:Descendiente izquierdo: 2 × i + BIT [ i ]Descendiente derecho: 2 × i + 1 - BIT [ i ]Así es como se ve. Los elementos cuyos descendientes se encuentran "viceversa" se resaltan en azul. Los valores en la matriz BIT para ellos son 1.Puede verificar sustituyendo los valores primarios i y el 0/1 correspondiente de la matriz BIT en las fórmulas descendientes : los índices de los descendientes aparecerán según sea necesario.Como puede ver, para que cualquier padre intercambie los subárboles izquierdo y derecho, en la matriz misma, el grupo de elementos no necesita moverse a ninguna parte. Solo se cambia el valor 0/1 para el padre en la matriz BIT y eso es todo.A continuación, una sesión de magia con su posterior exposición.Construye una pila débil
El intercambio de descendientes hacia la izquierda y hacia la derecha es la herramienta principal para convertir en un montón débil un conjunto de datos de una matriz.En el proceso de formar el montón débil primario, necesitamos clasificar los elementos de la matriz en el orden inverso (comenzando desde el último) y para cada uno de ellos encontrar la rama del primer padre (derecho), para el cual será el subárbol correcto.Si el elemento es el descendiente correcto de alguien , entonces no tiene que ir muy lejos. Su padre inmediato es lo que necesita:Si el elemento es el descendiente izquierdo de alguien , entonces debe subir varios niveles antes de encontrarse con el abuelo deseado, para el cual el elemento está en el subárbol correcto:Luego debe comparar el descendiente y el progenitor que se encuentra en algún lugar de arriba. Y si el descendiente es más grande que el progenitor, entonces se debe hacer lo siguiente:- Si el descendiente tiene sus propios descendientes, cambie sus subárboles izquierdo y derecho (es decir, cambie 0/1 en la matriz BIT para este elemento).
- Intercambie los valores del nodo descendiente y el nodo progenitor.
Echa un vistazo a un ejemplo específico. Digamos que surgió la siguiente situación:Para el elemento de la matriz A [6] = 87, se encontró el progenitor A [1] = 76 necesario.
El progenitor A [1] es más pequeño que el elemento A [6] (76 <87).
El elemento A [6] tiene subárboles izquierdo y derecho (marcados en tonos de verde).
Debe intercambiar estos subárboles
(es decir, para el elemento A [6] en la matriz BIT , cambie el valor de 0 a 1).
También es necesario intercambiar los valores de los elementos A [6] y A [1].Después de completar las acciones necesarias:Para el elemento A [6], se intercambiaron los subárboles izquierdo y derecho
(es decir, en la matriz BIT para el elemento A [6], el valor de 0 se cambió a 1).
También hubo un intercambio de valores entre A [6] y A [1].Si recorre la matriz desde el final hasta el principio y en el camino realiza este procedimiento para todos los elementos, terminará con un montón débil.Por qué funciona este extraño mecanismo es una explicación más cercana al final del artículo.Analizando una pila débil
Un montón es un montón si el elemento máximo está en la raíz. Usando este hecho, todas las clasificaciones de montón funcionan de la misma manera. La raíz (donde se encuentra el máximo) intercambia valores con el último elemento de la parte no ordenada de la matriz; como resultado, la parte no ordenada de la matriz disminuye y la parte ordenada de la matriz aumenta. Después de este intercambio, el montón deja de ser un montón, ya que el elemento máximo actual ya no está en su raíz. El montón necesita ser restaurado, es decir, hacer que el árbol resultante vuelva a ser un montón: encuentre otro elemento máximo y muévalo a la raíz.Sabemos cómo recuperar un montón binario regular, con la ayuda de un tamiz . Pero, ¿cómo restaurar un montón débil? Para hacer esto, haga lo siguiente.Desde la raíz descendemos hacia los descendientes izquierdos (hasta el más bajo):Luego subimos los descendientes izquierdos hacia atrás y en el camino cada descendiente izquierdo se compara con un elemento en la raíz del montón. Y si el siguiente descendiente izquierdo es más grande que la raíz, entonces hacemos lo mismo que en la etapa anterior: en el descendiente izquierdo intercambiamos los subárboles (si tiene uno) y cambiamos los valores del descendiente izquierdo y la raíz.Como resultado, restauraremos el montón débil: el elemento máximo que está en el árbol restante aparecerá en su raíz.Y nuevamente, tenemos este carrusel místico con subárboles que se reemplazan entre sí. Entonces, ¿cuál es el secreto del éxito? ¿Por qué, si durante el intercambio de nodos con valores, los descendientes izquierdo y derecho del nodo inferior se intercambian, terminamos con una matriz ordenada? Nunca lo adivinará, aunque la respuesta es simple en su genio.Clasificación de montón débil :: Clasificación de montón débil
Entonces, el algoritmo final:- I. :
- I.1. -.
- I.2. «» .
- I.3. .
- I.4. , :
- I.4.. ( ⇔ ) , .
- I.4.. «» .
- II. , :
- II.1. .
- II.2. . .
- II.3. , . :
- II.3.. .
- II.3.. , .
- II.3.. , , :
- II.3.c.1. Intercambiamos (izquierda ⇔ derecha) subárboles con descendientes para el nodo en el que se encuentra el descendiente izquierdo actual.
- II.3.c.2. Cambiamos la raíz del montón y el nodo con el hijo izquierdo actual.
- II.4. En la raíz del montón débil se encuentra nuevamente el elemento máximo para la parte no ordenada restante de la matriz. Volvemos al párrafo II.1 y repetimos el proceso hasta que todos los elementos estén ordenados.
Animación (los índices de matriz en mis animaciones comienzan con uno):Código C ++
Al final de la sección "Enlaces", los interesados pueden familiarizarse con la implementación de esta clasificación en C ++. Aquí solo doy la parte que ilustra el algoritmo en sí.#define GETFLAG(r, x) ((r[(x) >> 3] >> ((x) & 7)) & 1)
#define TOGGLEFLAG(r, x) (r[(x) >> 3] ^= 1 << ((x) & 7))
void WeakHeap::WeakHeapMerge(unsigned char *r, int i, int j) {
if (wheap[i] < wheap[j]) {
TOGGLEFLAG(r, j);
swap(wheap[i], wheap[j]);
}
}
void WeakHeap::WeakHeapSort() {
int n = Size();
if(n > 1) {
int i, j, x, y, Gparent;
int s = (n + 7) / 8;
unsigned char * r = new unsigned char [s];
for(i = 0; i < n / 8; ++i) r[i] = 0;
for(i = n - 1; i > 0; --i) {
j = i;
while ((j & 1) == GETFLAG(r, j >> 1)) j >>= 1;
Gparent = j >> 1;
WeakHeapMerge(r, Gparent, i);
}
for(i = n - 1; i >= 2; --i) {
swap(wheap[0], wheap[i]);
x = 1;
while((y = 2 * x + GETFLAG(r, x)) < i) x = y;
while(x > 0) {
WeakHeapMerge(r, 0, x);
x >>= 1;
}
}
swap(wheap[0], wheap[1]);
delete[] r;
}
}
Me gusta especialmente cómo se atraviesa el árbol binario de manera fácil y natural mediante operaciones bit a bit.Complejidad de memoria extra
Parece que O ( n ): se requiere una matriz adicional, en la que para los nodos con descendientes (hay aproximadamente la mitad de aquellos en la matriz), el orden de los subárboles izquierdo / derecho es fijo.Sin embargo, existe la opinión de que la complejidad de la clasificación aquí es en realidad O (1). Para un elemento, solo necesitamos un bit adicional (cero / uno) para indicar el orden de los descendientes. Si clasificamos, por ejemplo, cadenas, entonces es bastante factible agregar este bit adicional al elemento mismo.Otra forma de convertir O ( n ) en O (1) es almacenar banderas en un número entero. Expansión binaria de números: un conjunto de ceros y unos responsables del orden de los subárboles de todos los elementos de la matriz. El i- ésimo elemento de la matriz corresponde al i- ésimo bit del número.Complejidad de tiempo
Por tiempo, O ( n log n ) es lo mismo que un montón normal. Al ordenar las filas (especialmente las largas), un montón débil puede ser más rápido que un montón normal. Pero esto es si clasificamos las largas colas. Si clasificamos los números, entonces, según los rumores, un montón común es más rápido de administrar.Tamizar por completo
En la etapa de formación del montón débil inicial, por analogía con el montón habitual, la idea bastante obvia sugiere elevar elementos grandes lo más alto posible. Es decir, si intercambiamos los valores del nodo inferior y su ancestro, entonces sería lógico repetir de inmediato los pasos para el ancestro: encontrar el ancestro correcto más cercano para él y compararlo (y si también es necesario intercambiar valores + intercambio de subárboles). Y, si es posible, eleve un elemento grande hasta la raíz. Así es como se ve en la primera etapa (las acciones en la segunda etapa del algoritmo no cambian):El puntaje de complejidad temporal sigue siendo el mismo.Pila binomial
Todo lo que sucedió hasta este momento es un engaño, una ilusión. Por supuesto, realizamos formalmente algunas manipulaciones con el árbol binario allí, cambiamos los nodos con valores, reorganizamos los subárboles y todo eso. Sin embargo, el algoritmo tiene un doble fondo, que ahora analizaremos.Para comprender este tipo, debe comprender qué es realmente un montón débil.Si tomamos una matriz en la que el número de elementos es una potencia de dos, entonces el montón débil y el montón binomial construido sobre esta base son isomorfos.No mire el hecho de que un montón débil es binario, y binomial no lo es. En un montón débil, los subárboles izquierdo y derecho son esencialmente diferentes. El subárbol derecho es un descendiente en el sentido clásico, pero el subárbol izquierdo es más bien un "hermano". Aunque no. El subárbol izquierdo ni siquiera es un "hermano", sino un vector de "hermanos" con menos nodos.Sin embargo, el montón débil y el montón binomial no son 100% iguales, aunque son los parientes más cercanos. La diferencia es obvia si toma una matriz cuyo número de elementos no es igual a 2 n . La descomposición binomial de dicha matriz dará una lista conectada de varios montones ideales (el número de nodos en cada uno de ellos es una potencia de dos):Un montón débil en este caso será un árbol binario imperfecto:La pila binomial y la pila débil son hermanos gemelos. El ADN es el mismo, aunque en apariencia no se nota.Algoritmo secreto
Dado que un montón débil es un montón criptobinomial, barajar subárboles de repente encuentra una explicación simple.Con un montón débil, elimine el oropel pseudobinario y observe las relaciones reales entre los nodos en el estilo de montón binomial. Todo queda claro.De hecho:- No hay "debilidad", es un árbol de clasificación completo (no binario) en el que se logra y mantiene el principio "cualquier padre es mayor que cualquiera de sus descendientes".
- En todas las etapas, comparamos a los descendientes no con sus antepasados, sino con sus padres inmediatos.
- Lo que parece un intercambio de valores entre un descendiente y un antepasado + un intercambio de lugares de subárboles en un descendiente, resulta ser el intercambio de la relación misma (descendiente / padre). Si el nodo padre es más pequeño que el descendiente por valor, entonces el padre mismo se convierte en descendiente y el descendiente se convierte en padre.
Aquí hay una visualización honesta:En la proxima serie
El siguiente montón del que me gustaría hablar es mi favorito: el árbol cartesiano. Esto no es solo un montón, sino también un árbol de búsqueda binario . Pero luego, primero, en el próximo artículo, hay que aclarar algo interesante sobre los árboles BST. Y solo entonces, a través del artículo, y sobre la charla cartesiana.Referencias
Débil Montón , binomial Montón / binomial
Montón C ++ débil implementación Montón
Ronald D. Dutton: Página personal , UCF Perfil del Sitio Web
débil Montones y amigos: Desarrollos recientes
La débil estructura-Montón de datos: Las variantes y aplicaciones en el rendimiento de débil HeapSort adaptativo heapsort: Código fuente
Sergey Kopeliovich - Sala de conferencias - Pila débil (de 48:32 a 1:16:06)Artículos de la serie:
La clasificación de hoy se agrega a la aplicación AlgoLab por un grupo débil, que la usa: actualice el archivo de Excel con macros.En los comentarios a la celda con el nombre del tipo, puede especificar algunas configuraciones. Si configura siftup = 1, la clasificación utilizará la exploración completa en la primera etapa (por defecto siftup = 0).Si prescribe binomial = 1, entonces el árbol será un "montón binomial" (por defecto binomial = 0, es decir, solo un montón débil).