Análisis

Para analizar el costo amortizado de las operaciones usaremos la función potencial. Definiremos $\phi = 2\ell+a$, donde $\ell$ es el largo de la lista de árboles en el bosque y $a$ es la cantidad de celdas no vacías en el arreglo $A$ que se usa para la operación ExtractMin (se entiende que el arreglo está vacío durante las otras operaciones).

Tenemos $\phi_0=0$ al comenzar con la cola vacía. La operación de insertar incrementa $\phi$ en $2$, por lo que su costo amortizado sigue siendo $O(1)$. FindMin no cambia $\phi$, por lo que su costo amortizado es igual al costo real, $O(1)$. Heapify es una secuencia de inserciones, por lo que su costo real y amortizado es $O(n)$.

Para la operación Merge, debemos considerar un conjunto de colas, y $\phi$ se define como la suma de $2\ell+a$ sobre todas las colas. De esa manera, al realizar Merge esta función $\phi$ global no cambia, y el costo real $O(1)$ es también el costo amortizado.

Nuevamente, la operación compleja es ExtractMin. El primer paso es eliminar la raíz del árbol $B_k$ que contiene el mínimo e insertar sus hijos en la lista. Esto cuesta $c_i=k$ e incrementa el largo de la lista en $k-1$, con lo cual tenemos $\Delta\phi_i=2k-2$ y $\hat{c_i}=3k-2=O(\log n)$ (podríamos tener $c_i=1$ si representamos los hijos con una lista doblemente enlazada, pero esto no cambia el costo amortizado).

Luego reducimos la lista a un bosque binomial. Consideremos el costo amortizado de procesar cada nuevo árbol $B_k$. Si $A[k]$ está vacío, movemos el $B_k$ de la lista a $A[k]$, con lo cual tenemos un costo de $c_i=1$ para moverlo y $\Delta\phi_i=-1$, resultando un costo amortizado de $\hat{c_i}=0$. Si, en cambio, teníamos un árbol en $A[k]$, entonces lo sacamos de $A[k]$ y lo unimos con el árbol $B_k$ de la lista, reemplazando ese árbol por el árbol unión $B_{k+1}$, que reemplaza al $B_k$ de la lista. Tenemos un costo de $c_i=1$ y $\Delta\phi_i = -1$, con lo que nuevamente el costo amortizado es cero. Finalmente, movemos los $a \le \log n$ árboles no nulos de $A$ a la lista, lo que cuesta $a$ operaciones e incrementa $\phi$ en $a$ también, sumando $O(\log n)$ al costo amortizado. En total, la operación ExtractMin tiene un costo amortizado de $O(\log n)$.

Note que estamos asignando costo $c_i=1$ a diversas cantidades constantes de operaciones que realizamos. Se le puede asignar cualquier otro costo constante $c$ y redefinir $\phi = c(2\ell+a)$ para obtener el mismo resultado.