Montón de Fibonacci

Estructura de datos para operaciones de cola de prioridad

En informática , un montón de Fibonacci es una estructura de datos para operaciones de cola de prioridad , que consiste en una colección de árboles ordenados por montón . Tiene un mejor tiempo de ejecución amortizado que muchas otras estructuras de datos de cola de prioridad, incluyendo el montón binario y el montón binomial . Michael L. Fredman y Robert E. Tarjan desarrollaron los montones de Fibonacci en 1984 y los publicaron en una revista científica en 1987. Los montones de Fibonacci reciben su nombre de los números de Fibonacci , que se utilizan en su análisis de tiempo de ejecución.

Los tiempos amortizados de todas las operaciones en los montículos de Fibonacci son constantes, excepto delete-min . ^{[1] [2]} La eliminación de un elemento (que se usa con más frecuencia en el caso especial de eliminar el elemento mínimo) funciona en tiempo amortizado, donde es el tamaño del montículo. ^[2] Esto significa que, a partir de una estructura de datos vacía, cualquier secuencia de a operaciones de inserción y disminución de clave y b operaciones delete-min tomarían el peor tiempo posible, donde es el tamaño máximo del montículo. En un montículo binario o binomial, dicha secuencia de operaciones tomaría tiempo. Por lo tanto, un montículo de Fibonacci es mejor que un montículo binario o binomial cuando es más pequeño que por un factor no constante. También es posible fusionar dos montículos de Fibonacci en tiempo amortizado constante, mejorando el tiempo de fusión logarítmico de un montículo binomial y mejorando los montículos binarios que no pueden manejar fusiones de manera eficiente. ${\displaystyle O(\log n)}$ ${\displaystyle n}$ ${\displaystyle O(a+b\log n)}$ ${\displaystyle n}$ ${\displaystyle O((a+b)\log n)}$ ${\displaystyle b}$ ${\displaystyle a}$

El uso de montículos de Fibonacci mejora el tiempo de ejecución asintótico de los algoritmos que utilizan colas de prioridad. Por ejemplo, el algoritmo de Dijkstra y el algoritmo de Prim pueden ejecutarse a tiempo. ${\displaystyle O(|E|+|V|\log |V|)}$

Estructura

Figura 1. Ejemplo de un montón de Fibonacci. Tiene tres árboles de grados 0, 1 y 3. Se marcan tres vértices (mostrados en azul). Por lo tanto, el potencial del montón es 9 (3 árboles + 2 × (3 vértices marcados)).

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 siempre está 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 manera perezosa , posponiendo el trabajo para operaciones posteriores. Por ejemplo, la fusión de montones se realiza simplemente concatenando las dos listas de árboles, y la operación de disminución de clave a veces corta un nodo de su padre y forma un nuevo árbol.

Sin embargo, en algún momento es necesario introducir orden en el montón para lograr el tiempo de ejecución deseado. En particular, los grados de los nodos (aquí grado significa el número de hijos directos) se mantienen bastante bajos: cada nodo tiene grado como máximo y el tamaño de un subárbol enraizado en un nodo de grado es al menos , donde es el número de Fibonacci . Esto se logra mediante la regla: como máximo, se puede cortar un hijo de cada nodo que no sea 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 (ver Demostración de límites de grado, a continuación). El número de árboles se reduce en la operación delete-min , donde los árboles se vinculan entre sí. ${\displaystyle \log n}$ ${\displaystyle k}$ ${\displaystyle F_{k+2}}$ ${\displaystyle F_{i}}$ ${\displaystyle i}$

Como resultado de una estructura relajada, algunas operaciones pueden tardar 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 suponemos que las operaciones muy rápidas tardan un poco más de lo que realmente tardan. Este tiempo adicional se combina y se resta del tiempo de ejecución real de las operaciones lentas. La cantidad de tiempo ahorrado 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 ${\displaystyle \phi }$

${\displaystyle \phi =t+2m}$,

donde es el número de árboles en el montón de Fibonacci y es el número de nodos marcados. Un nodo está marcado si al menos uno de sus hijos fue cortado, ya que este nodo se convirtió en hijo de otro nodo (todas las raíces no están marcadas). El tiempo amortizado para una operación está dado por la suma del tiempo real y multiplicado por la diferencia de potencial, donde c es una constante (elegida para coincidir con los factores constantes en la notación O mayúscula para el tiempo real). ${\displaystyle t}$ ${\displaystyle m}$ ${\displaystyle c}$

De esta forma, la raíz de cada árbol de un montón tiene almacenada una unidad de tiempo. Esta unidad de tiempo puede utilizarse posteriormente para vincular este árbol con otro árbol en el tiempo amortizado 0. Además, cada nodo marcado tiene almacenadas dos unidades de tiempo. Una puede utilizarse para separar el nodo de su padre. Si esto ocurre, el nodo se convierte en raíz y la segunda unidad de tiempo permanecerá almacenada en él como en cualquier otra raíz.

Operaciones

Para permitir una rápida eliminación y concatenación, las raíces de todos los árboles están vinculadas mediante una lista circular doblemente enlazada . 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.

Buscar-min

Mantenemos un puntero a la raíz que contiene la clave mínima, lo que permite el acceso al mínimo. Este puntero debe actualizarse durante las demás operaciones, lo que solo agrega una sobrecarga de tiempo constante. ${\displaystyle O(1)}$

Unir

La operación de fusión simplemente concatena las listas de raíces de dos montones y establece que el mínimo sea el más pequeño de los dos. Esto se puede hacer en tiempo constante y el potencial no cambia, lo que conduce nuevamente a un tiempo amortizado constante.

Insertar

La operación de inserción puede considerarse un caso especial de la operación de fusión, con un solo nodo. El nodo simplemente se añade a la lista raíz, lo que aumenta el potencial en uno. El costo amortizado, por lo tanto, sigue siendo constante.

Eliminar-min

Figura 2. Primera fase de delete-min .

Figura 3. Tercera fase de delete-min .

La operación delete-min realiza la mayor parte del trabajo de restauración de la estructura del montón. Tiene tres fases:

1. Se elimina la raíz que contiene el elemento mínimo y cada uno de sus hijos se convierte en una nueva raíz. El procesamiento de estas nuevas raíces lleva tiempo y el potencial aumenta en . Por lo tanto, el tiempo de ejecución amortizado de esta fase es . ${\displaystyle d}$ ${\displaystyle O(d)}$ ${\displaystyle d-1}$ ${\displaystyle O(d)=O(\log n)}$
2. Puede haber hasta raíces. Por lo tanto, disminuimos el número de raíces uniendo sucesivamente raíces del mismo grado. Cuando dos raíces tienen el mismo grado, hacemos que la que tiene la clave más grande sea hija de la otra, de modo que se observe la propiedad de montón mínimo. El grado de la raíz más pequeña aumenta 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 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 , donde es el número de raíces al comienzo de la segunda fase. Al final, tendremos como máximo raíces (porque cada una tiene un grado diferente). Por lo tanto, la diferencia en el potencial de antes a después de esta fase es . Por lo tanto, el tiempo de ejecución amortizado es . Al elegir un suficientemente grande de modo que los términos en se cancelen, esto se simplifica a . ${\displaystyle n}$ ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n+m)}$ ${\displaystyle m}$ ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)-m}$ ${\displaystyle O(\log n+m)+c(O(\log n)-m)}$ ${\displaystyle c}$ ${\displaystyle m}$ ${\displaystyle O(\log n)}$
3. Busque en la lista final de raíces para encontrar el mínimo y actualice el puntero mínimo en consecuencia. Esto lleva tiempo, porque se ha reducido la cantidad de raíces. ${\displaystyle O(\log n)}$

En total, el tiempo amortizado de esta operación es , siempre que . La prueba de ello se da en el apartado siguiente. ${\displaystyle O(\log n)}$ ${\displaystyle d=O(\log n)}$

Tecla de disminución

Figura 4. Montón de Fibonacci de la Figura 1 después de disminuir la clave del nodo 9 a 0.

Si al disminuir la clave de un nodo se vuelve más pequeño que su padre, se lo separa de su padre y se convierte en una nueva raíz sin marcar. Si también es menor que la clave mínima, se actualiza el puntero mínimo. ${\displaystyle x}$

A continuación, iniciamos una serie de cortes en cascada , comenzando con el padre de . Mientras el nodo actual esté marcado, se corta de su padre y se convierte en una raíz sin marcar. A continuación, se considera su padre original. Este proceso se detiene cuando llegamos a un nodo sin marcar . Si no es una raíz, se marca. En este proceso introducimos una cierta cantidad, digamos , de árboles nuevos. Excepto posiblemente , cada uno de estos árboles nuevos pierde su marca original. El nodo final puede quedar marcado. Por lo tanto, el cambio en la cantidad de nodos marcados está entre de y . El cambio resultante en el potencial es . El tiempo real requerido para realizar el corte fue . Por lo tanto, el tiempo amortizado es , que es constante, siempre que sea suficientemente grande. ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle k}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle -k}$ ${\displaystyle -k+2}$ ${\displaystyle k+2(-k+2)=-k+4}$ ${\displaystyle O(k)}$ ${\displaystyle O(k)+c(-k+4)}$ ${\displaystyle c}$

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, siendo , donde es el tamaño del montón. Aquí mostramos que el tamaño del (sub)árbol enraizado en cualquier nodo de grado en el montón debe tener un tamaño de al menos , donde es el número de Fibonacci . El límite de grado se deduce de esto y del hecho (fácilmente demostrado por inducción) de que para todos los números enteros , donde es la proporción áurea . Entonces tenemos , y tomando el logaritmo de la base de ambos lados da como se requiere. ${\displaystyle O(\log n)}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle d}$ ${\displaystyle F_{d+2}}$ ${\displaystyle F_{i}}$ ${\displaystyle i}$ ${\displaystyle F_{d+2}\geq \varphi ^{d}}$ ${\displaystyle d\geq 0}$ ${\displaystyle \varphi =(1+{\sqrt {5}})/2\approx 1.618}$ ${\displaystyle n\geq F_{d+2}\geq \varphi ^{d}}$ ${\displaystyle \varphi }$ ${\displaystyle d\leq \log _{\varphi }n}$

Sea un nodo arbitrario en un montón de Fibonacci, no necesariamente una raíz. Definamos que sea el tamaño del árbol con raíz en (el número de descendientes de , incluido él mismo). Demostramos por inducción sobre la altura de (la longitud del camino más largo desde hasta una hoja descendiente) que , donde es el grado de . ${\displaystyle x}$ ${\displaystyle \mathrm {size} (x)}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle \mathrm {size} (x)\geq F_{d+2}}$ ${\displaystyle d}$ ${\displaystyle x}$

Caso base: Si tiene altura , entonces , y . ${\displaystyle x}$ ${\displaystyle 0}$ ${\displaystyle d=0}$ ${\displaystyle \mathrm {size} (x)=1\geq F_{2}}$

Caso inductivo: Supongamos que tiene altura y grado positivos . Sean los hijos de , ordenados en orden de las veces que se convirtieron en hijos de más recientemente ( siendo el primero y el último), y sean sus respectivos grados. ${\displaystyle x}$ ${\displaystyle d>0}$ ${\displaystyle y_{1},y_{2}\dots y_{d}}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle y_{1}}$ ${\displaystyle y_{d}}$ ${\displaystyle c_{1},c_{2}\dots c_{d}}$

Afirmamos que para cada . Justo antes de que se convirtiera en hijo de , ya eran hijos de , y por lo tanto deben haber tenido grado al menos en ese momento. Dado que los árboles se combinan solo cuando los grados de sus raíces son iguales, debe haber sido el caso de que también tuviera grado al menos en el momento en que se convirtió en hijo de . Desde ese momento hasta el presente, solo podría haber perdido como máximo un hijo (como lo garantiza el proceso de marcado), y por lo tanto su grado actual es al menos . Esto prueba la afirmación. ${\displaystyle c_{i}\geq i-2}$ ${\displaystyle i}$ ${\displaystyle y_{i}}$ ${\displaystyle x}$ ${\displaystyle y_{1}\dots y_{i-1}}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle i-1}$ ${\displaystyle y_{i}}$ ${\displaystyle i-1}$ ${\displaystyle x}$ ${\displaystyle y_{i}}$ ${\displaystyle c_{i}}$ ${\displaystyle i-2}$

Como las alturas de todos los son estrictamente menores que la de , podemos aplicarles la hipótesis inductiva para obtener Los nodos y cada uno contribuye al menos en 1 a , y así tenemos donde el último paso es una identidad para los números de Fibonacci. Esto da el límite inferior deseado en . ${\displaystyle y_{i}}$ ${\displaystyle x}$ $${\displaystyle \mathrm {size} (y_{i})\geq F_{c_{i}+2}\geq F_{(i-2)+2}=F_{i}.}$$ ${\displaystyle x}$ ${\displaystyle y_{1}}$ ${\displaystyle \mathrm {size} (x)}$ $${\displaystyle {\begin{aligned}\mathrm {size} (x)&\geq 2+\sum _{i=2}^{d}\mathrm {size} (y_{i})\\&\geq 2+\sum _{i=2}^{d}F_{i}\\&=1+\sum _{i=0}^{d}F_{i}\\&=F_{d+2}\end{aligned}}}$$ ${\displaystyle \mathrm {size} (x)}$

Actuación

Aunque los montículos de Fibonacci parecen muy eficientes, tienen las dos desventajas siguientes: ^[3]

1. Son complicadas de implementar.
2. En la práctica, no son tan eficientes en comparación con formas de montículos teóricamente menos eficientes. ^[4] En su versión más simple, requieren la manipulación de cuatro punteros por nodo, mientras que en otras estructuras, como el montículo binomial o el montículo de emparejamiento , solo se necesitan dos o tres punteros por nodo . Esto da como resultado un gran consumo de memoria por nodo y factores constantes elevados en todas las operaciones.

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 indicados anteriormente, algunas operaciones (muy pocas) de la secuencia pueden tardar mucho tiempo en completarse (en particular, delete-min tiene un tiempo de ejecución lineal en el peor de los casos). Por este motivo, los montículos de Fibonacci y otras estructuras de datos amortizadas pueden no ser adecuadas 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 montón de Fibonacci, que tiene un rendimiento amortizado. Una de esas estructuras, la cola de Brodal , ^[5] es, en palabras del creador, "bastante complicada" y "[no] aplicable en la práctica". Inventado en 2012, el montón de Fibonacci estricto ^[6] 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 ser más simple, los experimentos muestran que en la práctica el montón de Fibonacci estricto tiene un rendimiento 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. ^{[7] [8]} Los montones relajados de ejecución de Driscoll et al. ofrecen un buen rendimiento en el peor de los casos para todas las operaciones del montón de Fibonacci, excepto la fusión. ^[9] Resultados experimentales recientes sugieren que el montón de Fibonacci es más eficiente en la práctica que la mayoría de sus derivados posteriores, incluidos los montones de terremotos, los montones de violación, los montones de Fibonacci estrictos y los montones de emparejamiento de rangos, pero menos eficiente que los montones de emparejamiento o los montones basados ​​en matrices. ^[8]

Resumen de tiempos de ejecución

Aquí se muestran las complejidades temporales ^[10] de varias estructuras de datos de montón. La abreviatura am. indica que la complejidad dada se amortiza, de lo contrario es una complejidad del peor caso. Para el significado de " O ( f )" y " Θ ( f )", consulte la notación Big O. Los nombres de las operaciones suponen un montón mínimo.

1. make-heap es la operación de construir un montón a partir de una secuencia de n elementos no ordenados. Se puede realizar en Θ ( n ) tiempo siempre que meld se ejecute en O (log  n ) tiempo (donde ambas complejidades se pueden amortizar). ^{[11] [12]} Otro algoritmo logra Θ ( n ) para montones binarios. ^[13]
2. Para los montículos persistentes (que no admiten decrease-key ), una transformación genérica reduce el costo de meld al de insert , mientras que el nuevo costo de delete-min es la suma de los costos anteriores de delete-min y meld . ^[16] Aquí, hace que meld se ejecute en Θ (1) tiempo (amortizado, si el costo de insert es) mientras que delete-min todavía se ejecuta en O (log  n ). Aplicado a montículos binomiales sesgados, produce colas Brodal-Okasaki, montículos persistentes con complejidades óptimas en el peor de los casos. ^[15]
3. Límite inferior de ^[19] límite superior de ^[20] ${\displaystyle \Omega (\log \log n),}$ ${\displaystyle O(2^{2{\sqrt {\log \log n}}}).}$
4. colas de Brodal y los montículos de Fibonacci estrictos logran complejidades óptimas en el peor de los casos para los montículos. Primero se describieron como estructuras de datos imperativas. La cola de Brodal-Okasaki es una estructura de datos persistente que logra el mismo óptimo, excepto que no se admite la clave de disminución .

Referencias

1. 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.
2. Fredman, Michael Lawrence ; Tarjan, Robert E. (julio de 1987). "Montones de Fibonacci y sus usos en algoritmos mejorados de optimización de redes" (PDF) . Revista de la Asociación de Maquinaria Computacional . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . doi :10.1145/28869.28874. 
3. 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) . Algorithmica . 1 (1–4): 111–129. doi :10.1007/BF01840439. S2CID  23664143.
4. http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/FibonacciHeaps.pdf, pág. 79
5. Gerth Stølting Brodal (1996), "Colas de prioridad eficientes en el peor de los casos", Proc. 7º Simposio ACM-SIAM sobre algoritmos discretos , Sociedad de Matemáticas Industriales y Aplicadas : 52–58, CiteSeerX 10.1.1.43.8133 , ISBN  0-89871-366-8
6. Brodal, GSL; Lagogiannis, G.; Tarjan, RE (2012). Montones de Fibonacci estrictos (PDF) . Actas del 44.º simposio sobre teoría de la computación - STOC '12. p. 1177. doi :10.1145/2213977.2214082. ISBN 978-1-4503-1245-5.
7. Mrena, Michal; Sedlacek, Peter; Kvassay, Miroslav (junio de 2019). "Aplicabilidad práctica de implementaciones avanzadas de colas de prioridad para encontrar rutas más cortas". Conferencia internacional sobre tecnologías de la información y digitales (IDT) de 2019. Zilina, Eslovaquia: IEEE. págs. 335–344. doi :10.1109/DT.2019.8813457. ISBN. 9781728114019. Número de identificación del sujeto  201812705.
8. Larkin, Daniel; Sen, Siddhartha; Tarjan, Robert (2014). "Un estudio empírico de vuelta a lo básico de las colas de prioridad". Actas del decimosexto taller sobre ingeniería de algoritmos y experimentos : 61–72. arXiv : 1403.0252 . Bibcode :2014arXiv1403.0252L. doi :10.1137/1.9781611973198.7. ISBN 978-1-61197-319-8. Número de identificación del sujeto  15216766.
9. Driscoll, James R.; Gabow, Harold N.; Shrairman, Ruth; Tarjan, Robert E. (noviembre de 1988). "Pilones relajados: una alternativa a los montículos de Fibonacci con aplicaciones a la computación paralela". Comunicaciones de la ACM . 31 (11): 1343–1354. doi : 10.1145/50087.50096 . S2CID  16078067.
10. 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.
11. Sleator, Daniel Dominic ; Tarjan, Robert Endre (febrero de 1986). "Montones autoajustables". Revista SIAM de informática . 15 (1): 52–69. CiteSeerX 10.1.1.93.6678 . doi :10.1137/0215004. ISSN  0097-5397. 
12. Tarjan, Robert (1983). "3.3. Montones de izquierdas". Estructuras de datos y algoritmos de red . págs. 38-42. doi :10.1137/1.9781611970265. ISBN 978-0-89871-187-5.
13. Hayward, Ryan; McDiarmid, Colin (1991). "Análisis de caso promedio de construcción de montículos mediante inserción repetida" (PDF) . J. Algorithms . 12 : 126–153. CiteSeerX 10.1.1.353.7888 . doi :10.1016/0196-6774(91)90027-v. Archivado desde el original (PDF) el 2016-02-05 . Consultado el 2016-01-28 . 
14. "Pila binomial | Wiki de matemáticas y ciencias brillante". brilliant.org . Consultado el 30 de septiembre de 2019 .
15. Brodal, Gerth Stølting; Okasaki, Chris (noviembre de 1996), "Colas de prioridad puramente funcionales óptimas", Journal of Functional Programming , 6 (6): 839–857, doi : 10.1017/s095679680000201x
16. Okasaki, Chris (1998). "10.2. Abstracción estructural". Estructuras de datos puramente funcionales (1.ª ed.). pp. 158-162. ISBN 9780521631242.
17. Takaoka, Tadao (1999), Teoría de 2-3 montones (PDF) , pág. 12
18. Iacono, John (2000), "Límites superiores mejorados para emparejar montones", Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF) , Apuntes de clase en informática, vol. 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
19. 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 Computacional . 46 (4): 473–501. doi :10.1145/320211.320214.
20. Pettie, Seth (2005). Towards a Final Analysis of Pairing Heaps (PDF) . FOCS '05 Actas del 46.º Simposio anual IEEE sobre fundamentos de la informática. pp. 174–183. CiteSeerX 10.1.1.549.471 . doi :10.1109/SFCS.2005.75. ISBN .  0-7695-2468-0.
21. Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (noviembre de 2011). "Montones de emparejamiento de rangos" (PDF) . SIAM J. Informática . 40 (6): 1463–1485. doi :10.1137/100785351.
22. Brodal, Gerth Stølting ; Lagogiannis, George; Tarjan, Robert E. (2012). Montones de Fibonacci estrictos (PDF) . Actas del 44.º simposio sobre 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.
23. Brodal, Gerth S. (1996), "Colas de prioridad eficientes en el peor de los casos" (PDF) , Actas del 7.º Simposio anual ACM-SIAM sobre algoritmos discretos , págs. 52-58
24. Goodrich, Michael T .; Tamassia, Roberto (2004). "7.3.6. Construcción de montículos ascendentes". Estructuras de datos y algoritmos en Java (3.ª ed.). págs. 338–341. ISBN 0-471-46983-1.

Enlaces externos

• Simulación de un montón de Fibonacci mediante un applet de Java
• Implementación de MATLAB del montón de Fibonacci
• Implementación en C des-recursiva y eficiente en el uso de la memoria del montón de Fibonacci (software libre, licencia CeCILL-B)
• Implementación en Ruby del montón de Fibonacci (con pruebas)
• Pseudocódigo del algoritmo del montón de Fibonacci