En informática , un montón de Fibonacci es una estructura de datos para operaciones de cola de prioridad , que consta de una colección de árboles ordenados por montones . Tiene un tiempo de ejecución mejor amortizado que muchas otras estructuras de datos de cola de prioridad, incluido el montón binario y el montón binomial . Michael L. Fredman y Robert E. Tarjan desarrollaron montones de Fibonacci en 1984 y los publicaron en una revista científica en 1987. Los montones de Fibonacci llevan el nombre de los números de Fibonacci , que se utilizan en su análisis de tiempo de ejecución.
Montón de Fibonacci | |||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Tipo | montón | ||||||||||||||||||||||||
Inventado | 1984 | ||||||||||||||||||||||||
Inventado por | Michael L. Fredman y Robert Endre Tarjan | ||||||||||||||||||||||||
Complejidad del tiempo en notación O grande | |||||||||||||||||||||||||
|
Para el montón de Fibonacci, la operación de encontrar mínimo toma un tiempo de amortización constante ( O (1)). [1] Las operaciones clave de inserción y disminución también funcionan en un tiempo amortizado constante. [2] Eliminar un elemento (usado con mayor frecuencia en el caso especial de eliminar el elemento mínimo) funciona en el tiempo amortizado O (log n ), donde n es el tamaño del montón. [2] Esto significa que a partir de una estructura de datos vacía, cualquier secuencia de una pieza de inserción y reducir las operaciones de clave y b operaciones de borrado tomarían O ( un + b log n ) peor caso el tiempo, donde n es el tamaño máximo del montón. En un montón binario o binomial, tal secuencia de operaciones tomaría O (( a + b ) log n ) tiempo. Por tanto, un montón de Fibonacci es mejor que un montón binario o binomial cuando b es menor que a por un factor no constante. También es posible fusionar dos montones de Fibonacci en un tiempo amortizado constante, mejorando el tiempo de fusión logarítmico de un montón binomial y mejorando los montones binarios que no pueden manejar fusiones de manera eficiente.
El uso de montones de Fibonacci para colas de prioridad mejora el tiempo de ejecución asintótico de algoritmos importantes, como el algoritmo de Dijkstra para calcular la ruta más corta entre dos nodos en un gráfico, en comparación con el mismo algoritmo que utiliza otras estructuras de datos de cola de prioridad más lentas.
Estructura
Un montón de Fibonacci es una colección de árboles que satisfacen la propiedad de montón mínimo , es decir, la clave de un hijo siempre es mayor o igual que la clave del padre. Esto implica que la clave mínima está siempre en la raíz de uno de los árboles. En comparación con los montones binomiales, la estructura de un montón de Fibonacci es más flexible. Los árboles no tienen una forma prescrita y, en el caso extremo, el montón puede tener cada elemento en un árbol separado. Esta flexibilidad permite que algunas operaciones se ejecuten de forma perezosa , posponiendo el trabajo para operaciones posteriores. Por ejemplo, la combinación de montones se realiza simplemente concatenando las dos listas de árboles, y la tecla de operación de disminución a veces corta un nodo de su padre y forma un nuevo árbol.
Sin embargo, en algún momento es necesario introducir un orden en el montón para lograr el tiempo de ejecución deseado. En particular, los grados de los nodos (aquí el grado significa el número de hijos directos) se mantienen bastante bajos: cada nodo tiene un grado como máximo log n y el tamaño de un subárbol enraizado en un nodo de grado k es al menos F k +2 , donde F k es el k- ésimo número de Fibonacci . Esto se logra mediante la regla de que podemos cortar como máximo un hijo de cada nodo no raíz. Cuando se corta un segundo hijo, el nodo en sí debe cortarse de su padre y se convierte en la raíz de un nuevo árbol (consulte Prueba de límites de grado, a continuación). El número de árboles se reduce en la operación eliminar mínimo , donde los árboles se vinculan entre sí.
Como resultado de una estructura relajada, algunas operaciones pueden llevar mucho tiempo mientras que otras se realizan muy rápidamente. Para el análisis del tiempo de ejecución amortizado utilizamos el método potencial , en el que pretendemos que las operaciones muy rápidas tardan un poco más de lo que realmente toman. Este tiempo adicional luego se combina y se resta del tiempo de ejecución real de las operaciones lentas. La cantidad de tiempo que se ahorra para su uso posterior se mide en un momento dado mediante una función potencial. El potencial de un montón de Fibonacci está dado por
- Potencial = t + 2 m
donde t es el número de árboles en el montón de Fibonacci y m es el número de nodos marcados. Un nodo se marca si al menos uno de sus hijos se cortó, ya que este nodo se convirtió en hijo de otro nodo (todas las raíces están desmarcadas). El tiempo amortizado para una operación viene dado por la suma del tiempo real y c multiplicado por la diferencia de potencial, donde c es una constante (elegida para coincidir con los factores constantes en la notación O para el tiempo real).
Por lo tanto, la raíz de cada árbol en un montón tiene una unidad de tiempo almacenada. Esta unidad de tiempo se puede utilizar más tarde para vincular este árbol con otro árbol en el tiempo amortizado 0. Además, cada nodo marcado tiene dos unidades de tiempo almacenadas. Se puede usar uno para cortar el nodo de su padre. Si esto sucede, el nodo se convierte en una raíz y la segunda unidad de tiempo permanecerá almacenada en él como en cualquier otra raíz.
Implementación de operaciones
Para permitir una rápida eliminación y concatenación, las raíces de todos los árboles se vinculan mediante una lista circular doblemente vinculada . Los hijos de cada nodo también están vinculados mediante dicha lista. Para cada nodo, mantenemos su número de hijos y si el nodo está marcado. Además, mantenemos un puntero a la raíz que contiene la clave mínima.
La operación buscar mínimo ahora es trivial porque mantenemos el puntero al nodo que lo contiene. No cambia el potencial del montón, por lo tanto, tanto el costo real como el amortizado son constantes.
Como se mencionó anteriormente, la combinación se implementa simplemente concatenando las listas de raíces de los dos montones. Esto se puede hacer en un tiempo constante y el potencial no cambia, lo que conduce nuevamente a un tiempo amortizado constante.
La operación insertar funciona creando un nuevo montón con un elemento y fusionando. Esto lleva un tiempo constante y el potencial aumenta en uno, porque aumenta el número de árboles. Por tanto, el coste amortizado sigue siendo constante.
La operación de extracción mínima (igual que eliminar mínima ) opera en tres fases. Primero tomamos la raíz que contiene el elemento mínimo y lo eliminamos. Sus hijos se convertirán en raíces de árboles nuevos. Si el número de hijos era d , se necesita tiempo O ( d ) para procesar todas las raíces nuevas y el potencial aumenta en d −1. Por lo tanto, el tiempo de ejecución amortizado de esta fase es O ( d ) = O (log n ).
Sin embargo, para completar la operación de extracción mínima, necesitamos actualizar el puntero a la raíz con la clave mínima. Desafortunadamente, puede haber hasta n raíces que debamos verificar. En la segunda fase, por lo tanto, disminuimos el número de raíces uniendo sucesivamente raíces del mismo grado. Cuando dos raíces u y v tienen el mismo grado, que hacen que uno de ellos un niño de otro modo que el que tiene la llave más pequeña sigue siendo la raíz. Su grado aumentará en uno. Esto se repite hasta que cada raíz tenga un grado diferente. Para encontrar árboles del mismo grado de manera eficiente, usamos una matriz de longitud O (log n ) en la que mantenemos un puntero a una raíz de cada grado. Cuando se encuentra una segunda raíz del mismo grado, las dos se vinculan y la matriz se actualiza. El tiempo de ejecución real es O (log n + m ) donde m es el número de raíces al comienzo de la segunda fase. Al final tendremos como máximo raíces O (log n ) (porque cada una tiene un grado diferente). Por lo tanto, la diferencia en la función potencial desde antes de esta fase hasta después de ella es: O (log n ) - m , y el tiempo de ejecución amortizado es entonces como máximo O (log n + m ) + c ( O (log n ) - m ). Con una elección suficientemente grande de c , esto se simplifica a O (log n ).
En la tercera fase comprobamos cada una de las raíces restantes y encontramos el mínimo. Esto lleva O (log n ) tiempo y el potencial no cambia. El tiempo de ejecución total amortizado del extracto mínimo es, por tanto, O (log n ).
La operación de disminución de clave tomará el nodo, disminuirá la clave y si la propiedad del montón se viola (la nueva clave es más pequeña que la clave del padre), el nodo se corta de su padre. Si el padre no es una raíz, está marcado. Si ya se ha marcado, también se corta y se marca su padre. Continuamos hacia arriba hasta llegar a la raíz o un nodo sin marcar. Ahora establecemos el puntero mínimo en el valor disminuido si es el nuevo mínimo. En el proceso creamos cierto número, digamos k , de árboles nuevos. Cada uno de estos árboles nuevos, excepto posiblemente el primero, se marcó originalmente, pero como raíz no se marcará. Un nodo puede quedar marcado. Por lo tanto, el número de nodos marcados cambia en - ( k - 1) + 1 = - k + 2. Combinando estos 2 cambios, el potencial cambia en 2 (- k + 2) + k = - k + 4. El tiempo real realizar el corte fue O ( k ), por lo tanto (nuevamente con una elección suficientemente grande de c ) el tiempo de funcionamiento amortizado es constante.
Finalmente, la operación borrar se puede implementar simplemente disminuyendo la clave del elemento a borrar a menos infinito, convirtiéndolo así en el mínimo de todo el montón. Luego llamamos a extraer mínimo para eliminarlo. El tiempo de ejecución amortizado de esta operación es O (log n ).
Prueba de límites de grado
El rendimiento amortizado de un montón de Fibonacci depende del grado (número de hijos) de cualquier raíz de árbol que sea O (log n ), donde n es el tamaño del montón. Aquí mostramos que el tamaño del (sub) árbol enraizado en cualquier nodo x de grado d en el montón debe tener un tamaño de al menos F d +2 , donde F k es el k- ésimo número de Fibonacci . El límite de grado se deriva de esto y del hecho (fácilmente probado por inducción) de que para todos los enteros , dónde . (Entonces tenemosy llevando el tronco a la base de ambos lados da según sea necesario.)
Considere cualquier nodo x en algún lugar del montón ( no es necesario que x sea la raíz de uno de los árboles principales). Defina tamaño ( x ) como el tamaño del árbol enraizado en x (el número de descendientes de x , incluido el propio x ). Demostramos por inducción sobre la altura de x (la longitud de un camino simple más largo desde x hasta una hoja descendiente), que el tamaño ( x ) ≥ F d +2 , donde d es el grado de x .
Caso base: si x tiene altura 0, entonces d = 0 y tamaño ( x ) = 1 = F 2 .
Caso inductivo: Suponga que x tiene altura positiva y grado d > 0. Sean y 1 , y 2 , ..., y d los hijos de x , indexados en el orden de las veces en que se hicieron hijos más recientemente de x ( y 1 siendo el más antiguo y y d el último), y sean c 1 , c 2 , ..., c d sus respectivos grados. Nosotros reivindicamos que c i ≥ i -2 para cada i con 2 ≤ i ≤ d : Justo antes de y i hicieron un niño de x , y 1 , ..., y i -1 eran ya hijos de x , y así x tenía al menos un grado i −1 en ese momento. Dado que los árboles se combinan solo cuando los grados de sus raíces son iguales, debe haber sido que y i también tenía un grado al menos i -1 en el momento en que se convirtió en un hijo de x . Desde ese momento hasta el presente, y i solo puede haber perdido como máximo un hijo (como lo garantiza el proceso de calificación), por lo que su grado actual c i es al menos i −2. Esto prueba la afirmación .
Dado que las alturas de todas las y i son estrictamente menores que las de x , podemos aplicarles la hipótesis inductiva para obtener tamaño ( y i ) ≥ F c i +2 ≥ F ( i −2) +2 = F i . Los nodos x y y 1 cada uno contribuyen al menos 1 a tamaño ( x ), y por lo que tenemos
Una inducción de rutina demuestra que para cualquier , que da el límite inferior deseado en el tamaño ( x ).
Peor de los casos
Aunque los montones de Fibonacci parecen muy eficientes, tienen los siguientes dos inconvenientes: [3]
- Son complicados a la hora de implementarlos.
- En la práctica, no son tan eficientes en comparación con las formas de montones teóricamente menos eficientes. En su versión más simple, requieren el almacenamiento y la manipulación de cuatro punteros por nodo, mientras que solo se necesitan dos o tres punteros por nodo en otras estructuras, como el montón binario , el montón binomial , el montón de emparejamiento , la cola de Brodal y el montón de emparejamiento de rango.
Aunque el tiempo total de ejecución de una secuencia de operaciones que comienza con una estructura vacía está limitado por los límites dados anteriormente, algunas (muy pocas) operaciones en la secuencia pueden tardar mucho en completarse (en particular, la eliminación y la eliminación mínima tienen un tiempo de ejecución lineal en el peor caso). Por esta razón, los montones de Fibonacci y otras estructuras de datos amortizadas pueden no ser apropiadas para sistemas en tiempo real . Es posible crear una estructura de datos que tenga el mismo rendimiento en el peor de los casos que el rendimiento amortizado del montón de Fibonacci. Una de esas estructuras, la cola de Brodal , [4] es, en palabras del creador, "bastante complicada" y "[no] aplicable en la práctica". Creado en 2012, el estricto montón de Fibonacci [5] es una estructura más simple (en comparación con la de Brodal) con los mismos límites en el peor de los casos. A pesar de tener una estructura más simple, los experimentos muestran que en la práctica el montón de Fibonacci estricto funciona más lento que la cola de Brodal más complicada y también más lento que el montón de Fibonacci básico. [6] [7] Los montones de carreras relajadas de Driscoll et al. dar un buen rendimiento en el peor de los casos para todas las operaciones de montón de Fibonacci, excepto la fusión.
Resumen de tiempos de ejecución
Aquí están las complejidades de tiempo [8] de varias estructuras de datos de pila. Los nombres de las funciones asumen un min-heap. Para el significado de " O ( f )" y " Θ ( f )" ver Big O notación .
Operación | find-min | eliminar min | insertar | tecla de disminución | fusionar |
---|---|---|---|---|---|
Binario [8] | Θ (1) | Θ (log n ) | O (log n ) | O (log n ) | Θ ( n ) |
Izquierdista | Θ (1) | Θ (log n ) | Θ (log n ) | O (log n ) | Θ (log n ) |
Binomio [8] [9] | Θ (1) | Θ (log n ) | Θ (1) [a] | Θ (log n ) | O (log n ) [b] |
Fibonacci [8] [2] | Θ (1) | O (log n ) [a] | Θ (1) | Θ (1) [a] | Θ (1) |
Emparejamiento [10] | Θ (1) | O (log n ) [a] | Θ (1) | o (log n ) [a] [c] | Θ (1) |
Brodal [13] [d] | Θ (1) | O (log n ) | Θ (1) | Θ (1) | Θ (1) |
Emparejamiento de rango [15] | Θ (1) | O (log n ) [a] | Θ (1) | Θ (1) [a] | Θ (1) |
Fibonacci estricto [16] | Θ (1) | O (log n ) | Θ (1) | Θ (1) | Θ (1) |
2-3 montón [17] | O (log n ) | O (log n ) [a] | O (log n ) [a] | Θ (1) | ? |
- ^ a b c d e f g h i Tiempo amortizado.
- ^ n es el tamaño del montón más grande.
- ^ Límite inferior de[11] límite superior de[12]
- ^ Brodal y Okasaki describen más tarde unavariante persistente con los mismos límites, excepto para la tecla de disminución, que no es compatible. Los montones con n elementos se pueden construir de abajo hacia arriba en O ( n ). [14]
Consideraciones prácticas
Los montones de Fibonacci tienen la reputación de ser lentos en la práctica [18] debido al gran consumo de memoria por nodo y altos factores constantes en todas las operaciones. Los resultados experimentales recientes sugieren que los montones de Fibonacci son más eficientes en la práctica que la mayoría de sus derivados posteriores, incluidos los montones de terremotos, montones de violación, montones de Fibonacci estrictos, montones de emparejamiento de rangos, pero menos eficientes que los montones de emparejamiento o montones basados en matrices. [7]
Referencias
- ^ Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001) [1990]. "Capítulo 20: Montones de Fibonacci". Introducción a los algoritmos (2ª ed.). MIT Press y McGraw-Hill. págs. 476–497. ISBN 0-262-03293-7.Tercera edición p. 518.
- ^ a b c Fredman, Michael Lawrence ; Tarjan, Robert E. (julio de 1987). "Montones de Fibonacci y sus usos en algoritmos de optimización de red mejorados" (PDF) . Revista de la Asociación de Maquinaria Informática . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . doi : 10.1145 / 28869.28874 .
- ^ Fredman, Michael L .; Sedgewick, Robert ; Sleator, Daniel D .; Tarjan, Robert E. (1986). "El montón de emparejamiento: una nueva forma de montón autoajustable" (PDF) . Algoritmica . 1 (1–4): 111–129. doi : 10.1007 / BF01840439 . S2CID 23664143 .
- ^ Gerth Stølting Brodal (1996), "Colas de prioridad eficientes en el peor de los casos" , Proc. 7 ° Simposio ACM-SIAM sobre algoritmos discretos , Society for Industrial and Applied Mathematics : 52–58, CiteSeerX 10.1.1.43.8133 , doi : 10.1145 / 313852.313883 (inactivo el 31 de mayo de 2021), ISBN 0-89871-366-8Mantenimiento de CS1: DOI inactivo a partir de mayo de 2021 ( enlace )
- ^ Brodal, GSL; Lagogiannis, G .; Tarjan, RE (2012). Montones estrictos de Fibonacci (PDF) . Actas del 44º simposio de Teoría de la Computación - STOC '12. pag. 1177. doi : 10.1145 / 2213977.2214082 . ISBN 978-1-4503-1245-5.
- ^ Mrena, Michal; Sedlacek, Peter; Kvassay, Miroslav (junio de 2019). "Aplicabilidad práctica de implementaciones avanzadas de colas de prioridad en la búsqueda de rutas más cortas". 2019 Conferencia Internacional sobre Tecnologías de la Información y Digitales (IDT) . Zilina, Eslovaquia: IEEE: 335–344. doi : 10.1109 / DT.2019.8813457 . ISBN 9781728114019. S2CID 201812705 .
- ^ a b Larkin, Daniel; Sen, Siddhartha; Tarjan, Robert (2014). "Un estudio empírico de vuelta a los fundamentos de las colas de prioridad". Actas del Decimosexto Taller sobre Ingeniería de Algoritmos y Experimentos : 61–72. arXiv : 1403.0252 . Código bibliográfico : 2014arXiv1403.0252L . doi : 10.1137 / 1.9781611973198.7 . ISBN 978-1-61197-319-8. S2CID 15216766 .
- ^ a b c d Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. (1990). Introducción a los algoritmos (1ª ed.). MIT Press y McGraw-Hill. ISBN 0-262-03141-8.
- ^ "Binomial Heap | Wiki brillante de matemáticas y ciencias" . shiny.org . Consultado el 30 de septiembre de 2019 .
- ^ Iacono, John (2000), "Límites superiores mejorados para emparejar montones", Proc. Séptimo taller escandinavo sobre teoría de algoritmos (PDF) , Lecture Notes in Computer Science, 1851 , Springer-Verlag, págs. 63–77, arXiv : 1110.4428 , CiteSeerX 10.1.1.748.7812 , doi : 10.1007 / 3-540-44985-X_5 , ISBN 3-540-67690-2
- ^ Fredman, Michael Lawrence (julio de 1999). "Sobre la eficiencia de emparejar montones y estructuras de datos relacionadas" (PDF) . Revista de la Asociación de Maquinaria Informática . 46 (4): 473–501. doi : 10.1145 / 320211.320214 .
- ^ Pettie, Seth (2005). Hacia un análisis final de los montones de emparejamiento (PDF) . FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. págs. 174-183. CiteSeerX 10.1.1.549.471 . doi : 10.1109 / SFCS.2005.75 . ISBN 0-7695-2468-0.
- ^ Brodal, Gerth S. (1996), "Colas de prioridad eficientes en el peor de los casos" (PDF) , Proc. Séptimo Simposio Anual ACM-SIAM sobre Algoritmos Discretos , págs. 52–58
- ^ Goodrich, Michael T .; Tamassia, Roberto (2004). "7.3.6. Construcción de montón de abajo hacia arriba". Estructuras de datos y algoritmos en Java (3ª ed.). págs. 338–341. ISBN 0-471-46983-1.
- ^ Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (noviembre de 2011). "Montones de emparejamiento de rangos" (PDF) . SIAM J. Computación . 40 (6): 1463–1485. doi : 10.1137 / 100785351 .
- ^ Brodal, Gerth Stølting ; Lagogiannis, George; Tarjan, Robert E. (2012). Montones estrictos de Fibonacci (PDF) . Actas del 44º simposio de Teoría de la Computación - STOC '12. págs. 1177-1184. CiteSeerX 10.1.1.233.1740 . doi : 10.1145 / 2213977.2214082 . ISBN 978-1-4503-1245-5.
- ^ Takaoka, Tadao (1999), Teoría de 2-3 montones (PDF) , p. 12
- ^ http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/FibonacciHeaps.pdf , p. 79
enlaces externos
- Simulación de subprograma Java de un montón de Fibonacci
- Implementación de MATLAB del montón de Fibonacci
- Implementación C no recursiva y eficiente en memoria del montón de Fibonacci (software libre / libre, licencia CeCILL-B )
- Implementación de Ruby del montón de Fibonacci (con pruebas)
- Pseudocódigo del algoritmo de montón de Fibonacci
- Varias implementaciones de Java para el montón de Fibonacci