Saltar al contenido principal

Colas de Fibonacci

Las colas de Fibonacci son una variante de las colas binomiales que realizan la inserción y la unión en tiempo constante, mientras que la extracción del mínimo tiene un costo amortizado de O(log⁡n)O(\log n). Más precisamente, les corresponde la siguiente tabla (donde el asterisco significa tiempo amortizado).

ImplementacioˊnInsertFindMinExtractMinHeapifyMergeHeapslog⁡n1log⁡nnn+mCola binomiallog⁡n1log⁡nnlog⁡(n+m)Cola de Fibonacci11  log⁡n (∗) ⁣ ⁣ ⁣ ⁣ ⁣n1\begin{array}{|c||c|c|c|c|c|c|} \hline \text{Implementación} & \text{Insert} & \text{FindMin} & \text{ExtractMin} & \text{Heapify} & \text{Merge} \\ \hline \hline \text{Heaps} & \log n & 1 & \log n & n & n+m \\ \hline \text{Cola binomial} & \log n & 1 & \log n & n & \log(n+m) \\ \hline \text{Cola de Fibonacci} & 1 & 1 & ~~\log n~(*)\!\!\!\!\! & n & 1 \\ \hline \end{array}

La principal diferencia con las colas binomiales es que la cola de Fibonacci no es un bosque binomial, sino simplemente un bosque de árboles binomiales unidos en una lista doblemente enlazada. Es decir, la cola de Fibonacci puede tener varios árboles BkB_k del mismo tamaño. De hecho, una cola de Fibonacci construida mediante nn inserciones en una cola vacía no es más que un bosque de nn nodos simples. Todo el trabajo de estructurar la cola se realiza al momento de la extracción del mínimo.

Al igual que en la cola binomial, esta cola sabe cuál es la raíz del árbol que contiene el mínimo elemento.

--> imagen