Montículo de Fibonacci

Resulta similar a un montículo binomial, pero dispone de una mejor relación entre el coste y su amortización.

En particular, las operaciones Insertar, Encontrar el mínimo, Decrementar la clave, y la Unión trabajan con tiempo constante 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)).

Como resultado de esta estructura, algunas operaciones pueden llevar mucho tiempo mientras que otras se hacen muy deprisa.

Esta unidad de tiempo puede ser usada más tarde para unir este árbol a otro con coste amortizado 0.

Para cada nodo, guardamos el número de hijos y si está marcado.

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.

Esto se repite hasta que todas las raíces tienen un grado diferente.

Al final tendremos como mucho O(log n) raíces (porque cada una tiene grado diferente).

En la tercera fase, comprobamos cada una de las raíces restantes y encontramos el mínimo.

El tiempo medio de ejecución amortizado para extraer el mínimo es por consiguiente O(log n).

El tiempo para realizar el corte es O(k) y el tiempo de ejecución amortizado es constante.

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.
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.
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.
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.