Operaciones

Consideremos ahora una cola binomial $C_S$ con $n$ elementos, y veamos cómo realizar las operaciones.

Insert

Para insertar un elemento $x$, creamos una cola binomial $C = \{ B_0 \}$, con $B_0$ conteniendo el elemento $x$, y sumamos las colas $C_S$ y $C$ para formar el nuevo $C_S$. El elemento queda entonces insertado en tiempo $O(\log n)$.

FindMin

El mínimo de todos los elementos puede calcularse en tiempo $O(\log n)$, mediante recorrer las (a lo más) $\lceil \log_2 n \rceil$ raíces de los árboles del bosque binomial $C_S$, pues los elementos no-raíces no son menores que las raíces. Para reducir este tiempo a $O(1)$, basta tener precalculado el valor del mínimo: la recorrida de raíces se realiza como postproceso luego de realizar cualquiera de las otras operaciones que modifican $C_S$, y les agrega sólo un costo adicional de $O(\log n)$.

ExtractMin

Una vez que sabemos que el mínimo es la raíz de un árbol $B_k \in C_S$, sacamos $B_k$ del bosque y eliminamos su raíz. El resultado de eliminar la raíz de $B_k$ es un nuevo bosque binomial formado por los $k$ hijos de la raíz eliminada, $C_N=\{ B_0, \ldots, B_{k-1} \}$. Finalmente, sumamos las colas $C_S - \{ B_k \}$ y $C_N$, en tiempo $O(\log n)$, y el resultado es el nuevo $C_S$.

Heapify

La implementación de heaps tardaría tiempo $O(n\log n)$ en construir un heap mediante inserciones sucesivas, por lo que se diseña para ella un procedimiento especial para realizar esta operación en tiempo $O(n)$. Sin embargo, en una cola binomial obtenemos tiempo $O(n)$ si realizamos $n$ inserciones sucesivas en una cola vacía. La razón está en el análisis de los $2^k$ incrementos consecutivos en un número de $k$ bits que realizamos al comienzo del capítulo y que está en relación directa con los costos de inserción de esta cola.

Unir

La unión de dos colas binomiales de tamaños $m$ y $n$ se obtiene en tiempo $O(\log(m+n))$ mediante sumarlas. Con un heap clásico, la forma más fácil de unir dos colas de prioridad es concatenar los arreglos e invocar heapify, lo que cuesta tiempo $O(m+n)$.