En informática , un montón débil es una estructura de datos para colas de prioridad que combina características del montón binario y del montón binomial . Se puede almacenar en una matriz como un árbol binario implícito , como un montón binario, y tiene las garantías de eficiencia de los montones binomiales.
Un algoritmo de ordenamiento que utiliza montones débiles, weak-heapsort, utiliza un número de comparaciones que está cerca del límite inferior teórico del número de comparaciones necesarias para ordenar una lista , por lo que es particularmente útil cuando la comparación es costosa, como cuando se comparan cadenas utilizando el algoritmo de intercalación Unicode completo .
Un montón débil se entiende más fácilmente como un árbol multidireccional ordenado por montón y almacenado como un árbol binario que utiliza la convención "hijo derecho, hermano izquierdo". (Esto es equivalente, pero al revés, al árbol binario habitual de hijo izquierdo y hermano derecho ).
En el árbol multidireccional, y asumiendo un montón máximo, la clave de cada padre es mayor o igual a ( ≥ ) todas las claves de los hijos (y, por lo tanto, por inducción, todos los miembros del subárbol).
Expresado como un árbol binario, esto se traduce en los siguientes invariantes: [1]
La última condición es una consecuencia del hecho de que un árbol binario implícito es un árbol binario completo .
La estructura de este árbol se corresponde perfectamente con la disposición tradicional de árbol binario implícito basado en 1 (Ahnentafel), donde el nodo k tiene un hermano siguiente (hijo izquierdo) numerado 2k y un primer hijo (hijo derecho) numerado 2k + 1 , al agregar una raíz adicional numerada 0. Esta raíz no tiene hermanos, solo un primer hijo, que es el nodo 1 ( 2×0 + 1 ).
Esta estructura es muy similar a la de un montón binomial, con un árbol de altura h compuesto por una raíz más árboles de alturas h − 1 , h − 2 , ..., 1 . Un montón débil perfecto (sin hojas faltantes) con 2 n elementos es exactamente isomorfo a un montón binomial del mismo tamaño, [2] pero los dos algoritmos manejan tamaños que no son una potencia de 2 de manera diferente: un montón binomial usa múltiples árboles perfectos, mientras que un montón débil usa un solo árbol imperfecto.
Los montículos débiles requieren la capacidad de intercambiar los hijos izquierdo y derecho (y los subárboles asociados) de un nodo. En una representación explícita ( basada en punteros ) del árbol, esto es sencillo. En una representación implícita ( matriz ), esto requiere un "bit inverso" por nodo interno para indicar qué hijo se considera el hijo izquierdo. Por lo tanto, un montículo débil no es una estructura de datos estrictamente implícita, ya que requiere O ( n ) espacio adicional ( 1/2 bit por nodo). Sin embargo, a menudo es posible encontrar espacio para este bit adicional dentro de la estructura del nodo, por ejemplo, etiquetando un puntero que ya está presente.
En el árbol binario implícito, el nodo k con bit inverso r k tiene padre ⌊ a/2 ⌋ , hijo izquierdo 2 k + r k , y hijo derecho 2 k + 1 − r k .
Visto como un árbol multidireccional, cada nodo en un montón débil está vinculado a otros dos: un "próximo hermano" y un "primer hijo". En el árbol implícito, los vínculos son fijos, por lo que el bit inverso indica cuál de los dos vínculos es el hermano y cuál el primer hijo.
Tenga en cuenta que cada nodo de un montón débil puede considerarse la raíz de un montón débil más pequeño ignorando su siguiente nodo hermano. Los nodos sin un primer nodo hijo son automáticamente nodos débiles válidos.
Un nodo de altura h tiene h − 1 hijos: un primer hijo de altura h − 1 , un segundo hijo de altura h − 2 , y así sucesivamente hasta el último hijo de altura 1 . Estos se pueden encontrar siguiendo el primer enlace hijo y luego los enlaces hermanos sucesivos.
También tiene hermanos siguientes de altura h − 1 , h − 2 , etc.
El padre de un nodo en el árbol multidireccional se denomina "antepasado distinguido". Para encontrarlo en el árbol binario, busque el padre binario del nodo. Si el nodo es el hijo derecho (primer hijo), el padre es el antepasado distinguido. Si el nodo es el hijo izquierdo (próximo hermano), su antepasado distinguido es el mismo que el de su padre binario. En el árbol implícito, encontrar al padre binario es fácil, pero se debe consultar su bit inverso para determinar qué tipo de hijo es el nodo. (Los primeros documentos utilizaban el término "abuelo" para el antepasado distinguido, [3] un significado confusamente diferente del habitual "padre del padre").
Aunque el ancestro distinguido puede estar a log 2 n niveles de altura en el árbol, la distancia promedio es 2. (Es al menos 1 , y la mitad del tiempo recurrimos, por lo que D = 1 + D /2 , lo que significa que D = 2 ). Por lo tanto, incluso un algoritmo iterativo simple para encontrar el ancestro distinguido es suficiente.
Al igual que los montones binomiales, la operación fundamental en los montones débiles es fusionar dos montones de igual altura h para formar un montón débil de altura h +1 . Esto requiere exactamente una comparación entre las raíces. La raíz que sea mayor (suponiendo un montón máximo) es la raíz final. Su primer hijo es la raíz perdedora, que conserva sus hijos (subárbol derecho). Los hijos de la raíz ganadora se instalan como hermanos de la raíz perdedora.
Esta operación se puede realizar en la estructura de árbol implícita porque los montones que se fusionan nunca son arbitrarios. En cambio, los dos montones se forman como parte de la clasificación de un nodo en el árbol multidireccional:
Al principio, las invariantes del montón se aplican en todas partes, excepto posiblemente entre la primera raíz y su antecesor distinguido. Todos los demás nodos son menores o iguales que sus antecesores distinguidos.
Después de comparar las dos raíces, la fusión se realiza de una de dos maneras:
El segundo caso funciona porque, en el árbol multidireccional, cada nodo conserva a sus hijos. La primera raíz asciende en el árbol porque es mayor que su antecesor distinguido. Por lo tanto, es mayor que todos los hijos anteriores del antecesor.
Sin embargo, el ancestro anterior no es un padre seguro para los hijos antiguos de la primera raíz, porque es menor que la primera raíz y, por lo tanto, no se garantiza que sea mayor o igual que todos sus hijos.
Al intercambiar los hijos binarios, el subconjunto apropiado de los hijos antiguos del ancestro degradado (que son con seguridad menores o iguales que él) se degradan con él. Los nuevos hermanos del ancestro degradado son los hijos antiguos de la primera raíz, promovidos, que son con seguridad menores o iguales que la primera raíz promovida.
Después de esta operación, no es seguro si se mantiene la invariante entre el nuevo ancestro distinguido y su ancestro distinguido, por lo que la operación se repite hasta que se llega a la raíz.
Los montones débiles se pueden utilizar para ordenar una matriz, esencialmente de la misma manera que un heapsort convencional . [3] Primero, se construye un montón débil a partir de todos los elementos de la matriz, y luego la raíz se intercambia repetidamente con el último elemento, que se tamiza hasta su lugar apropiado.
Se puede formar un montón débil de n elementos en n − 1 fusiones. Se puede hacer en varios órdenes, pero una implementación simple de abajo hacia arriba funciona desde el final de la matriz hasta el principio, fusionando cada nodo con su ancestro distinguido. Tenga en cuenta que la búsqueda del ancestro distinguido se simplifica porque los bits inversos en todos los padres de los montones que se están fusionando no se modifican desde su estado inicial ("no se invierten") y, por lo tanto, no es necesario consultarlos.
Al igual que con el heapsort, si la matriz a ordenar es más grande que la memoria caché de la CPU , el rendimiento mejora si los subárboles se fusionan tan pronto como dos del mismo tamaño estén disponibles, en lugar de fusionar todos los subárboles en un nivel antes de proceder al siguiente. [4]
La clasificación descendente en un montón débil se puede realizar en comparaciones h = ⌈log 2 n ⌉ , a diferencia de 2 log 2 n para un montón binario, o 1,5 log 2 n para la variante de " ordenación ascendente del montón ". Esto se hace "fusionando hacia arriba": después de intercambiar la raíz con el último elemento del montón, busque el último hijo (altura 1) de la raíz. Fusione este con la raíz (su ancestro distinguido), lo que da como resultado un montón de altura 2 válido en la raíz global. Luego vaya al hermano anterior (padre binario) del último nodo fusionado y fusione nuevamente. Repita hasta que se alcance la raíz, cuando será correcto para el árbol completo.
En un montón máximo débil, el valor máximo se puede encontrar (en tiempo constante) como el valor asociado con el nodo raíz; de manera similar, en un montón mínimo débil, el valor mínimo se puede encontrar en la raíz.
Al igual que con los montones binarios, los montones débiles pueden soportar las operaciones típicas de una estructura de datos de cola de prioridad : insertar, eliminar-min, eliminar o disminuir-clave, en tiempo logarítmico por operación.
La clasificación se realiza mediante el mismo proceso que en los montículos binarios. El nuevo nodo se agrega en el nivel de hoja, luego se compara con su antecesor distinguido y se intercambia si es necesario (operación de fusión). Esto se repite hasta que no sean necesarios más intercambios o se llegue a la raíz.
Las variantes de la estructura del montón débil permiten inserciones y claves decrecientes en tiempo amortizado constante, coincidiendo con el tiempo de los montones de Fibonacci . [2]
Dutton (1993) introdujo los montículos débiles como parte de un algoritmo de ordenamiento de montículos variante que (a diferencia del ordenamiento de montículos estándar que utiliza montículos binarios) podía utilizarse para ordenar n elementos utilizando solo n comparaciones log 2 n + O ( n ) . [3] [5] Posteriormente se investigaron como una estructura de datos de cola de prioridad de aplicación más general. [6] [7]
Ofrecemos un catálogo de algoritmos que optimizan los algoritmos estándar de varias maneras. Como criterios de optimización, consideramos el tiempo de ejecución en el peor de los casos, la cantidad de instrucciones, las predicciones erróneas de bifurcaciones, los errores de caché, las comparaciones de elementos y los movimientos de elementos.