Suma de colas

La primitiva crucial en colas binomiales es la suma, que dadas dos colas binomiales $C_X$ y $C_Y$ para conjuntos de elementos $X$ e $Y$ entrega una cola binomial $C_S$ para el conjunto $X \cup Y$ (permitimos claves duplicadas, de modo que esta unión no elimina repetidos). La suma procede análogamente a la suma de los números binarios $|X|$ y $|Y|$, partiendo con $C_S = \emptyset$ y considerando los bits en cada posición $k$ de $|X|$ y $|Y|$, desde el bit menos significativo ($k=0$) al más significativo. Llevaremos también un conjunto $T$ de 0 ó 1 árboles de acarreo, análogo al bit de carry de la suma binaria. Al comenzar tenemos $T=\emptyset$.

1. Si el $k$-ésimo bit de $|X|$ es 1, mover el árbol $B_k$ de $C_X$ a $T$.
2. Si el $k$-ésimo bit de $|Y|$ es 1, mover el árbol $B_k$ de $C_Y$ a $T$.

Luego, procesamos el $T$ resultante de la siguiente forma:

1. Si $|T|=0$, no hacer nada para este valor de $k$.
2. Si $|T|=1$, mover el árbol $B_k$ de $T$ a $C_S$, dejando $T=\emptyset$.
3. Si $|T|=2$, unir los dos árboles $B_k$ y $B_k'$ de $T$ en un árbol $B_{k+1}$, colgando el que tenga mayor raíz del que tenga menor raíz. El resultado es el nuevo contenido de $T$ para el siguiente valor de $k$.
4. Si $|T|=3$, elegir un árbol $B_k$ de los tres y moverlo a $C_S$. Con los otros dos, proceder como en el punto anterior.

--> imagen

La suma requiere entonces de tiempo $O(\log(|X \cup Y|))$, y deja los conjuntos $C_X$, $C_Y$ y $T$ vacíos, y el resultado de la suma en $C_S$.