Operaciones

Insert

Para insertar un elemento $x$ en una cola $C_S$, simplemente se crea un nuevo árbol $B_0$ conteniendo $x$ y se agrega este $B_0$ a la lista de árboles de $C_S$. Además se compara $x$ con el mínimo elemento, para actualizar el mínimo de ser necesario. El tiempo total es $O(1)$.

FindMin

Como siempre conocemos el mínimo elemento, el tiempo es $O(1)$.

Heapify

Se realiza mediante $n$ inserciones, en tiempo $O(n)$.

Merge

Simplemente se unen los dos conjuntos concatenando las dos listas, en tiempo $O(1)$. Además se comparan los dos mínimos, para retener el mínimo global.

ExtractMin

Ésta es la operación más compleja. Aquí recorremos la lista y nos aseguramos de convertirla en un bosque binomial, mediante sumar árboles iguales iterativamente.

Primero eliminamos la raíz del árbol $B_k$ que contiene el mínimo actual (la cual conocemos) y agregamos los hijos $B_0,\ldots,B_{k-1}$ a la lista de árboles de $C_S$.

Luego, convertimos el bosque de árboles binomiales en un bosque binomial. Para ello, creamos un pequeño arreglo $A$ de $\lceil \log_2 n \rceil$ punteros, donde $A[k]$ apunta a un único árbol $B_k$ si es que tenemos alguno. Inicialmente todos los punteros son nulos. Ahora recorremos la lista. Para cada árbol $B_k$ que encontramos, si $A[k]$ es nulo, asignamos $A[k] \leftarrow B_k$. Si no, unimos $B_k$ con el árbol $A[k]$ (colgando la raíz mayor de la menor) en un único árbol $B_{k+1}$, dejamos $A[k]$ en nulo y continuamos el proceso con este nuevo árbol $B_{k+1}$.

Al final de esta operación tenemos un bosque binomial en $A$, y creamos una lista enlazada con ellos. Ésta es la nueva cola de Fibonacci (en este momento es una cola binomial válida). Sobre las $O(\log n)$ raíces resultantes calculamos el nuevo mínimo y lo recordamos.

---

---

---