montón de fibonacci

Estructura de datos para operaciones de cola prioritaria.

En informática , un montón de Fibonacci es una estructura de datos para operaciones de cola prioritarias , que consta de una colección de árboles ordenados en montón . Tiene un mejor tiempo de ejecución amortizado que muchas otras estructuras de datos de colas 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 del tiempo de ejecución.

Los tiempos de amortización de todas las operaciones en los montones de Fibonacci son constantes, excepto eliminar-min . ^{[1] [2]} Eliminar un elemento (usado con mayor frecuencia en el caso especial de eliminar el elemento mínimo) funciona en tiempo amortizado, donde es el tamaño del montón. ^[2] Esto significa que a partir de una estructura de datos vacía, cualquier secuencia de operaciones de inserción y disminución de clave y b operaciones de eliminación mínima tomaría el peor de los casos, donde es el tamaño máximo del montón. En un montón binario o binomial, esa secuencia de operaciones llevaría tiempo. Por tanto, un montón de Fibonacci es mejor que un montón binario o binomial cuando es más pequeño que en 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. ${\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 montones de Fibonacci mejora el tiempo de ejecución asintótica de los algoritmos que utilizan colas de prioridad. Por ejemplo, se puede hacer que el algoritmo de Dijkstra y el algoritmo de Prim se ejecuten en el tiempo. ${\displaystyle O(|E|+|V|\log |V|)}$

Estructura

Figura 1. Ejemplo de montón de Fibonacci. Tiene tres árboles de grados 0, 1 y 3. Se marcan tres vértices (se muestran 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 preestablecida y, en casos extremos, el montón puede tener cada elemento en un árbol separado. Esta flexibilidad permite que algunas operaciones se ejecuten de forma diferida , 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 tecla 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 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 un grado como máximo y el tamaño de un subárbol enraizado en un nodo de grado es al menos , donde está 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 convertirse en la raíz de un nuevo árbol (consulte Prueba de límites de grado, a continuación). La cantidad de árboles disminuye en la operación eliminar-min , donde los árboles están vinculados 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 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 tardan. Este tiempo adicional luego se combina y se resta del tiempo de ejecución real de las operaciones lentas. La cantidad de tiempo ahorrado para un 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 se marca 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 de una operación viene dado por la suma del tiempo real multiplicado por la diferencia de potencial, donde c es una constante (elegida para coincidir con los factores constantes en la notación O grande para el tiempo real). ${\displaystyle t}$ ${\displaystyle m}$ ${\displaystyle c}$

Por tanto, la raíz de cada árbol de un montón tiene una unidad de tiempo almacenada. Esta unidad de tiempo se puede utilizar posteriormente 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 utilizar uno para cortar el nodo de su padre. Si esto sucede, el nodo pasa a ser raíz y la segunda unidad de tiempo quedará 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 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.

encontrar-min

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

Unir

La operación de fusión simplemente concatena las listas raíz de dos montones y establece el mínimo para que sea el más pequeño de los dos montones. Esto se puede hacer en tiempo constante y el potencial no cambia, lo que lleva 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 único nodo. El nodo simplemente se agrega a la lista raíz, aumentando el potencial en uno. Por tanto, el coste amortizado sigue siendo constante.

Eliminar-min

Figura 2. Primera fase de delete-min .

Figura 3. Tercera fase de delete-min .

La operación de eliminación mínima realiza la mayor parte del trabajo de restauración de la estructura del montón. Tiene tres fases:

1. La raíz que contiene el elemento mínimo se elimina y cada uno de sus hijos se convierte en una nueva raíz. Se necesita tiempo para procesar estas nuevas raíces y el potencial aumenta en . Por 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, convertimos a la que tiene la clave más grande en 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 se actualiza la matriz. 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 de potencial entre antes y después de esta fase es . Por tanto, el tiempo de ejecución amortizado es . Al elegir un valor lo suficientemente grande como para que los términos 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 el número de raíces. ${\displaystyle O(\log n)}$

En conjunto, el tiempo amortizado de esta operación es de , siempre que . La prueba de ello se da en el siguiente apartado. ${\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 la disminución de la clave de un nodo hace que se vuelva más pequeño que su padre, entonces se corta de su padre y se convierte en una nueva raíz sin marcar. Si también es menor que la clave mínima, entonces se actualiza el puntero mínimo. ${\displaystyle x}$

Luego 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. Luego se considera su padre original. Este proceso se detiene cuando llegamos a un nodo no marcado . Si no es raíz, se marca. En este proceso introducimos una cierta cantidad, digamos , de árboles nuevos. Excepto posiblemente , cada uno de estos nuevos árboles pierde su marca original. El nodo terminal puede quedar marcado. Por tanto, el cambio en el número de nodos marcados está entre of y . El cambio de potencial resultante es . El tiempo real requerido para realizar el corte fue de . Por 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 , 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 al menos , donde está el ené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 números enteros , ¿dónde está la proporción áurea ? Luego tenemos , y llevando el tronco a la base de ambos lados le damos lo necesario. ${\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. Definido como el tamaño del árbol enraizado (el número de descendientes de , incluido él mismo). Probamos por inducción sobre la altura de (la longitud del camino más largo desde 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 , indexados en orden de las veces en que fueron hijos 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}}$

Reclamamos eso para cada uno . Justo antes se hizo hijo de él , ya eran hijos de él , por lo que debían haber tenido título al menos en ese momento. Dado que los árboles se combinan sólo cuando los grados de sus raíces son iguales, debe haber ocurrido que también tenía grado al menos en el momento en que se convirtió en hijo de . Desde ese momento hasta el presente, sólo podría haber perdido como máximo un hijo (como lo garantiza el proceso de calificación), por lo que su grado actual es de 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}$

Dado que las alturas de todos los son estrictamente menores que las de , podemos aplicarles la hipótesis inductiva para obtener los nodos y cada uno contribuye al menos 1 a , por lo que tenemos que 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 las pilas de Fibonacci parecen muy eficientes, tienen los dos inconvenientes siguientes: ^[3]

1. Son complicados de implementar.
2. No son tan eficientes en la práctica en comparación con formas de montones 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ón binomial o el montón 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 (muy pocas) operaciones en la secuencia pueden tardar mucho en completarse (en particular, eliminar-mínimo tiene un tiempo de ejecución lineal en el peor caso). Por este motivo, los montones de Fibonacci y otras estructuras de datos amortizados pueden no ser apropiados 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 , ^[5] es, en palabras del creador, "bastante complicada" y "[no] aplicable en la práctica". Inventado en 2012, el montón estricto de Fibonacci ^[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 funciona más lento que la cola Brodal más complicada y también más lento que el montón de Fibonacci básico. ^{[7] [8]} Los montones de carreras relajadas de Driscoll et al. Proporciona 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 violaciones, 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

A continuación se presentan las complejidades temporales ^[10] de varias estructuras de datos del montón. La abreviatura soy. indica que la complejidad dada se amortiza; de lo contrario, es la complejidad del peor de los casos. Para conocer el significado de " O ( f )" y " Θ ( f )", consulte la notación O grande . 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 sin clasificar. Se puede hacer en tiempo Θ ( n ) siempre que la combinación se ejecute en tiempo O (log  n ) (donde ambas complejidades se pueden amortizar). ^{[11] [12]} Otro algoritmo logra Θ ( n ) para montones binarios. ^[13]
2. Para montones persistentes (que no admiten disminución-key ), una transformación genérica reduce el costo de fusionar al de insertar , mientras que el nuevo costo de eliminar-min es la suma de los costos anteriores de eliminar-min y fusionar . ^[16] Aquí, fusiona se ejecuta en Θ (1) tiempo (amortizado, si el costo de inserción lo es) mientras que delete-min todavía se ejecuta en O (log  n ). Aplicado a montones binomiales sesgados, produce colas de Brodal-Okasaki, montones 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. Las colas Brodal y los montones estrictos de Fibonacci logran complejidades óptimas en el peor de los casos para los montones. Primero fueron descritos como estructuras de datos imperativas. La cola 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ág. 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 de Computación . 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) . Algorítmica . 1 (1–4): 111–129. doi :10.1007/BF01840439. S2CID  23664143.
4. http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/FibonacciHeaps.pdf, p. 79
5. Gerth Stølting Brodal (1996), "Colas de prioridad eficientes en el peor de los casos", Proc. Séptimo 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 estrictos de Fibonacci (PDF) . Actas del 44º simposio sobre Teoría de la Computación - STOC '12. pag. 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 prioritarias para encontrar rutas más cortas". 2019 Conferencia Internacional sobre Tecnologías de la Información y Digitales (IDT) . Zilina, Eslovaquia: IEEE. págs. 335–344. doi :10.1109/DT.2019.8813457. ISBN 9781728114019. S2CID  201812705.
8. Larkin, Daniel; Sen, Siddhartha; Tarjan, Robert (2014). "Un estudio empírico de regreso a lo básico sobre colas prioritarias". Actas del decimosexto taller sobre experimentos e ingeniería de algoritmos : 61–72. arXiv : 1403.0252 . Código Bib : 2014arXiv1403.0252L. doi :10.1137/1.9781611973198.7. ISBN 978-1-61197-319-8. S2CID  15216766.
9. Driscoll, James R.; Gabow, Harold N.; Shrairman, Ruth; Tarjan, Robert E. (noviembre de 1988). "Montones relajados: una alternativa a los montones de Fibonacci con aplicaciones al cálculo paralelo". 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 Computación . 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 izquierda". 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 creación de montón mediante inserción repetida" (PDF) . J. Algoritmos . 12 : 126-153. CiteSeerX 10.1.1.353.7888 . doi :10.1016/0196-6774(91)90027-v. Archivado desde el original (PDF) el 5 de febrero de 2016 . Consultado el 28 de enero de 2016 . 
14. "Montón binomial | Wiki brillante de matemáticas y ciencias". brillante.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.). págs. 158-162. ISBN 9780521631242.
17. Takaoka, Tadao (1999), Teoría de 2 a 3 montones (PDF) , p. 12
18. Iacono, John (2000), "Límites superiores mejorados para emparejar montones", Proc. Séptimo taller escandinavo sobre teoría de algoritmos (PDF) , Apuntes de conferencias sobre 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 del emparejamiento de montones y estructuras de datos relacionadas" (PDF) . Revista de la Asociación de Maquinaria de Computación . 46 (4): 473–501. doi :10.1145/320211.320214.
20. Pettie, Seth (2005). Hacia un análisis final de los montones de emparejamiento (PDF) . FOCS '05 Actas del 46º Simposio anual del IEEE sobre fundamentos de la informática. págs. 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 estrictos de Fibonacci (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) , Proc. Séptimo 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ón ascendente". Estructuras de datos y algoritmos en Java (3ª ed.). págs. 338–341. ISBN 0-471-46983-1.

enlaces externos

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