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 + Y$ (esta es la suma de multiconjuntos, donde las multiplicidades de elementos se suman). La suma procede análogamente a la suma de los números binarios $|X|$ y $|Y|$, partiendo con $C_S \gets \emptyset$ y considerando los bits en cada posición $k$ de $x=|X|$ e $y=|Y|$, desde el bit menos significativo ($k=0$) al más significativo. Llevaremos también un conjunto $T$ que contiene los árboles $B_k$'s que se están sumando en la posición $k$, incluyendo un árbol de acarreo si es necesario (análogo al bit de carry de la suma binaria). Al comenzar tenemos $T\gets\emptyset$. Para cada $k$ hacemos lo siguiente.

1. Si el $k$-ésimo bit de $x$ es 1, movemos el árbol $B_k$ de $C_X$ a $T$.
2. Si el $k$-ésimo bit de $y$ es 1, movemos el árbol $B_k$ de $C_Y$ a $T$.
3. Si $|T|=0$, no hacemos nada para este valor de $k$.
4. Si $|T|=1$, movemos el árbol $B_k$ de $T$ a $C_S$, dejando $T\gets\emptyset$.
5. Si $|T|=2$, unimos 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$.
6. Si $|T|=3$, elegimos un árbol $B_k$ de los tres y lo movemos a $C_S$. Con los otros dos, procedemos como en el punto anterior.

---

---

---

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