Montículo de Fibonacci

En Informática, un Montículo de Fibonacci (o Heap de Fibonacci) es una estructura de datos subconjunto de los montículos, que a su vez, son un subconjunto especial dentro de los bosques de árboles. Resulta similar a un montículo binomial, pero dispone de una mejor relación entre el coste y su amortización. Los montículos de Fibonacci fueron desarrollados en 1984 por Michael L. Fredman y Robert E. Tarjan y publicados por primera vez en una revista científica en 1987. El nombre de montículos de Fibonacci viene de la sucesión de Fibonacci, que se usa en pruebas comparativas de tiempo (Benchmarking).

En particular, las operaciones Insertar, Encontrar el mínimo, Decrementar la clave, y la Unión trabajan con tiempo constante amortizado. Las operaciones Borrar y Borrar el mínimo tienen un coste O(log n) como coste amortizado. Esto significa que, empezando con una estructura de datos vacía, cualquier secuencia de a operaciones del primer grupo y b operaciones del segundo grupo tardarían O(a + b log n). En un montículo binomial cualquier secuencia de operaciones tardarían O((a + b)log (n)). Un montículo de Fibonacci es mejor que un montículo binomial cuando b es asintóticamente más pequeño que a.

El montículo de Fibonacci puede ser utilizado para mejorar el tiempo de ejecución asintótico del algoritmo de Dijkstra para calcular el camino más corto en un grafo y el algoritmo de Prim para calcular el árbol mínimo de un grafo.

Figura 1. Ejemplo de un montículo de Fibonacci. Tiene tres árboles de grados 0, 1 y 3. Tres vértices están marcados (mostrados en azul). Por lo tanto, el potencial de la pila es de 9.

Un Heap de Fibonacci es una colección de árboles que satisfacen la propiedad del orden mínimo del montículo (que para abreviar se suele utilizar el anglicismo "Min-Heap"), es decir, a grandes rasgos, la clave de un hijo es siempre mayor o igual que la de su padre. Esto implica que la clave mínima está siempre en la raíz. Comparado con los montículos binomiales, la estructura de un montículo de Fibonacci es más flexible. Los árboles no tienen una forma predefinida y en un caso extremo el heap puede tener cada elemento en un árbol separado o en un único árbol de profundidad n. Esta flexibilidad permite que algunas operaciones puedan ser ejecutadas de una manera "perezosa", posponiendo el trabajo para operaciones posteriores. Por ejemplo, la unión de dos montículos se hace simplemente concatenando las dos listas de árboles, y la operación Decrementar Clave a veces corta un nodo de su padre y forma un nuevo árbol.

Sin embargo, se debe introducir algún orden para conseguir el tiempo de ejecución deseado. En concreto, el grado de los nodos(el número de hijos) se tiene que mantener bajo: cada nodo tiene un grado máximo de O(log n) y la talla de un subárbol cuya raíz tiene grado k es por lo menos F_k + 2 , donde F_k es un número de Fibonacci. Esto se consigue con la regla de que podemos cortar como mucho un hijo de cada nodo no raíz. Cuando es cortado un segundo hijo, el nodo también necesita ser cortado de su padre y se convierte en la raíz de un nuevo árbol. El número de árboles se decrementa en la operación Borrar mínimo, donde los árboles están unidos entre sí.

Como resultado de esta estructura, algunas operaciones pueden llevar mucho tiempo mientras que otras se hacen muy deprisa. En el análisis del coste de ejecución amortizado pretendemos que las operaciones muy rápidas tarden un poco más de lo que tardan. Este tiempo extra se resta después al tiempo de ejecución de operaciones más lentas. La cantidad de tiempo ahorrada para un uso posterior es medida por una función potencial. Esta función es:

Potencial = t + 2m

Donde t es el número de árboles en el montículo de Fibonacci, y m es el número de nodos marcados. Un nodo está marcado si al menos uno de sus hijos se cortó desde que el nodo se fue hecho hijo de otro nodo (todas las raíces están desmarcadas).

Además, la raíz de cada árbol en un montículo tiene una unidad de tiempo almacenada. Esta unidad de tiempo puede ser usada más tarde para unir este árbol a otro con coste amortizado 0. Cada nodo marcado también tiene dos unidades de tiempo almacenadas. Una puede ser usada para cortar el nodo de su padre. Si esto sucede, el nodo se convierte en una raíz y la segunda unidad de tiempo se mantendrá almacenada como en cualquier otra raíz.

Para permitir un Borrado y Concatenado rápido, las raíces de todos los árboles están unidas una lista de tipo circular doblemente enlazada. Los hijos de cada nodo también están unidos usando una lista. Para cada nodo, guardamos el número de hijos y si está marcado. Además guardamos un puntero a la raíz que contiene la clave mínima.

La operación Encontrar Mínimo es trivial porque guardamos el puntero al nodo que lo contiene. Esto no cambia el Potencial del Montículo, ya que el coste actual y amortizado es constante. Tal como se indica arriba, la Unión se implementa simplemente concatenando las listas de raíces de árboles de los dos Heaps. Esto se puede hacer en tiempo constante y no cambia su Potencia, resultando otra vez un tiempo constante amortizado. La operación Insertar trabaja creando un nuevo montículo con un elemento y haciendo la Unión. Esto se hace en tiempo constante, y el Potencial se incrementa en 1, ya que el número de árboles aumenta. El tiempo amortizado es constante igualmente.

El montículo de Fibonacci de la figura 1 después de la primera fase de extracción mínima. El nodo con clave 1 (el mínimo) se ha eliminado y sus hijos han formado árboles por separado.

La operación Extraer Mínimo (lo mismo que Borrar Mínimo) opera en tres fases. Primero cogemos la raíz con el elemento mínimo y la borramos. Sus hijos se convertirán en raíces de nuevos árboles. Si el número de hijos era d, lleva un tiempo O(d) procesar todas las nuevas raíces y el Potencial se incrementa en d-1. El tiempo de ejecución amortizado en esta fase es O(d) = O(log n).

El montículo de Fibonacci de la figura 1 después de extraer el mínimo. En primer lugar, los nodos 3 y 6 están unidos entre sí. Entonces el resultado se vincula con árboles arraigados en el nodo 2. Por último, el nuevo mínimo se encuentra.

Sin embargo, para completar la extracción del mínimo, necesitamos actualizar el puntero a la raíz con la clave mínima. El problema es que hay n raíces que comprobar. En la segunda fase decrementamos el número de raíces agrupando sucesivamente las raíces del mismo grado. Cuando dos raíces u y v tienen el mismo grado, hacemos que una de ellas sea hija de la otra de manera que la que tenga la clave menor siga siendo la raíz. Su grado se incrementará en uno. Esto se repite hasta que todas las raíces tienen un grado diferente. Para encontrar árboles del mismo grado eficientemente usamos un vector de longitud O(log n) en el que guardamos un puntero a una raíz de cada grado. Cuando una segunda raíz con el mismo grado es encontrada, las dos se unen y se actualiza el vector. El tiempo de ejecución actual es O(log n + m) donde m es el número de raíces al principio de la segunda fase. Al final tendremos como mucho O(log n) raíces (porque cada una tiene grado diferente). Así pues el Potencial se decrementa al menos m - O(log n) y el tiempo de ejecución amortizado es O(log n).

En la tercera fase, comprobamos cada una de las raíces restantes y encontramos el mínimo. Esto cuesta O(log n) y el potencial no cambia. El tiempo medio de ejecución amortizado para extraer el mínimo es por consiguiente O(log n).

El montículo de Fibonacci de la figura 1 después de la disminución de los principales nodos de 9 a 0. Este nodo, así como sus dos antecesores marcados se cortan del árbol enraizado en el 1 y se colocan como nuevas raíces.

La operación Decrementar Clave cogerá el nodo, decrementará la clave y se viola la propiedad del montículo (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, se marca. Si ya estaba marcado, se corta también y su padre se marca. Continuamos subiendo hasta que, o bien alcanzamos la raíz o un vértice no marcado. En el proceso creamos un número k de nuevos árboles. El Potencial se reduce en al menos k − 2. El tiempo para realizar el corte es O(k) y el tiempo de ejecución amortizado es constante.

Por último, la operación Borrar puede ser implementada simplemente decrementando la clave del elemento a borrar a menos infinito, convirtiéndolo en el mínimo de todo el montículo, entonces llamamos a Extraer Mínimo para borrarlo. El tiempo de ejecución amortizado de esta operación es O(log n).

Aunque el tiempo total de ejecución de una secuencia de operaciones que empiezan por una estructura vacía viene determinado por lo explicado anteriormente, algunas, aunque muy pocas, operaciones de la secuencia pueden llevar mucho tiempo(en particular Decrementar Clave, Borrar y Borrar Mínimo tienen tiempo de ejecución lineal en el peor caso). Por este motivo los montículos de Fibonacci y otras estructuras con costes amortizados pueden no ser apropiadas para sistemas de tiempo real.

(*)Tiempo Amortizado

1. Fredman M. L. & Tarjan R. E. (1987). Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM 34(3), 596-615.
2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 20: Fibonacci Heaps, pp.476–497.
3. Brodal, G. S. 1996. Worst-case efficient priority queues. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Atlanta, Georgia, United States, January 28 - 30, 1996). Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, 52-58.

1. Simulación en Java de un Heap de Fibonacci
2. Implementación en C de un Heap de Fibonacci
3. Algoritmo en pseudocódigo del montículo de Fibonacci
4. Pseudocódigo y explicacion de J. Boyer (Dr. Dobb's Algorithm Alley)

1. Fibonacci (Leonardo de Pisa)