Estructura

Definimos el árbol binomial $B_k$ como una topología, de la siguiente forma:

• $B_0$ es un árbol formado por un único nodo.
• $B_{k+1}$ es un árbol $B_k$ al que se cuelga de la raíz otro hijo más, que resulta ser la raíz de otro árbol $B_k$.

--> imagen

Es fácil demostrar por inducción las siguientes propiedades:

• La cantidad de nodos en $B_k$ es $2^k$.
• La altura de $B_k$ es $k+1$ (entendiendo que un único nodo tiene altura 1).
• El árbol $B_k$ tiene ${k \choose i}$ nodos a profundidad $i$ (entendiendo que la raíz se encuentra a profundidad 0).
• La raíz de $B_k$ tiene $k$ hijos, $B_0,\ldots,B_{k-1}$.

Definimos un bosque binomial como un conjunto de árboles binomiales $\{ B_{k_1}, \ldots, B_{k_r} \}$ donde ningún par de árboles tiene el mismo tamaño, es decir, $k_i \not= k_j$ para todo $i \not= j$. Tenemos entonces las siguientes propiedades, también fáciles de ver:

• Existe exactamente un bosque binomial de tamaño $n$ para cada $n \ge 0$: la única combinación posible es tomar los $B_{k_i}$ tal que los 1s en la descomposición binaria de $n$ están en las posiciones $k_i$, partiendo de cero y de derecha a izquierda. Por ejemplo, el único bosque binomial de $n=5=101_2$ nodos es $\{ B_2, B_0 \}$.

--> imagen

• Un bosque binomial de $n$ nodos tiene a lo más $\lceil \log_2 n \rceil$ árboles binomiales.

Una cola binomial para un conjunto de $n$ elementos es un bosque binomial de $n$ nodos donde se almacena un elemento en cada nodo, cumpliendo que si $x$ está almacenado en el padre del nodo donde está almacenado $y$, entonces $x \le y$.