Algoritmo Heap Binomial

Algoritmo Heap Binomial

Consta de 9 operaciones que desarrolladas e implementadas logran la ejecución y experimentación de lo que el algoritmo puede hacer.

1. Make-binomial-heap()
2.Binomial-heap-minimum(H)
3. Binomial-link(y, z)
4. Binomial- heap-merge(H1, H2)
5. Binomial-heap-union(H1, H2)
6. Binomial-heap-insert(H, x)
7. Binomial-heap-extract-min(H)
8.Binomial-heap-decrease-key(H, x, k)
9. Binomial-heap-delete(H, x)

Funcionamiento del heap binomial el cual se componen de un bosque de árboles binomiales. Estos se definen recursivamente yaparecen a lo sumo una vez en el bosque. Un árbol binomial Bk es un árbol ordenado donde B0 consiste en un único nodo, B1 se compone de dos árboles Bk-1, donde uno de los dos está dosado a la raíz del otrocomo su hijo extremo derecho. Pero primero debemos conocer el concepto de heap, el cual nos dice que es un árbol binario semicompleto en el que el valor de la clave almacenado en cualquier nodo esmenor o igual que los valores de clave de sus hijos. Esta estructura de datos es más compleja a comparación del heap binario pero ofrece una mayor eficiencia en la fusión de dos heaps, haciendo que eltiempo de ejecución se reduzca a O (log n).Este consta de algunas operaciones como son: insertar, eliminar, crear heap, extraer mínimo, enlace y unión.

HEAP BINOMIAL

Un montículo binomial es unacolección de árboles Binomiales
Un árbol binomial, Bk , se define recursivamente:
B0 es un solo nodo
Bk consiste en dos árboles binomiales Bk-1 enlazados de la siguiente forma: laraíz de uno es elhijo más a la izquierda de la raíz del otro.

 

Propiedades del árbol binomial Bk:
tiene 2k nodos;
su altura es k;
tiene nodos en el nivel i, para i = 0, 1, …, k;
la raíz tiene grado k(número de hijos) y es el nodo de máximo grado; más aún, si se numeran los hijos de la raíz de izquierda a derecha como k –1, k –2,…, 0, el hijo i es la raíz de un subárbol Bi.

Demostración de las...