montón de fibonacci
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 montón . 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.
Para el montón de Fibonacci, la operación de búsqueda del mínimo requiere un tiempo amortizado constante ( O (1)). [1] Las operaciones de tecla de inserción y disminución también funcionan en tiempo constante amortizado. [2] Eliminar un elemento (usado con mayor frecuencia en el caso especial de eliminar el elemento mínimo) funciona en O (log n ) tiempo amortizado, 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 operaciones de inserción y disminución de teclas y b operaciones de eliminación tomaría O ( a + b log n) tiempo en el peor de los casos, donde n es el tamaño máximo de almacenamiento dinámico. En un montón binario o binomial, tal secuencia de operaciones tomaría O (( a + b ) log n ) tiempo. Por lo 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 las 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 usa otras estructuras de datos de cola de prioridad más lentas.
Un montón de Fibonacci es una colección de árboles que satisfacen la propiedad del 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 todos los elementos 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 disminución de operación a veces corta un nodo de su padre y forma un nuevo árbol.
Sin embargo, en algún momento se debe introducir el 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 como máximo un grado log n y el tamaño de un subárbol arraigado 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í necesita ser cortado de su padre y se convierte en la raíz de un nuevo árbol (ver Prueba de límites de grado, más abajo). Se disminuye el número de árboles en la operación.eliminar mínimo , donde los árboles están vinculados 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 , usamos 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 su uso posterior se mide en un momento dado por una función potencial. El potencial de un montón de Fibonacci viene dado por
