Heap Binomial

Un árbol binomial de orden k (Bk) tiene: nodos a la profundidad i.

Esto se logra fácilmente debido a la estructura de los mismos.

Como cada heap tiene a lo sumo log n árboles binomiales y mezclar dos árboles se puede implementar en O(1) el orden de la mezcla es O(log n).

Usando un puntero adicional al árbol binomial que contiene la menor llave en la raíz se puede implementar esta operación en O(1).

El puntero debe ser actualizado cuando se ejecute cualquier acción distinta de Find Min.

Esto se puede hacer en O(log n) sin incrementar el orden de las otras operaciones.

Si este es el caso se intercambia el elemento con su padre hasta que la propiedad sea cumplida o el nodo sea la raíz del árbol, esta actualización se conoce también como HEAPIFY en los Heaps Binarios.

En la figura se muestra una comparación en los costos de cada operación entre el Heap binomial y el binario.