Proyecto Unidad I - Binomial Heap

UNIVERSIDAD NACIONAL DE TRUJILLO FACULTAD DE CIENCIAS FISICAS Y MATEMATICAS ESCUELA DE INFORMATICA

BINOMIAL HEAP Profesor: Jorge Luis Guevara Díaz

PROYECTO DE INVESTIGACIÓN SOBRE EL ALGORITMO DE HEAP BINOMIAL. Karen Sofía Acate Venegas Email: [email protected]

Karina Vanessa Chico Moscol Email: [email protected]

Juan Benjamín Ganoza Campos Email: benjamí[email protected]

Charl Jóhanson López Egúsquiza Email: [email protected]

RESUMEN: En el presente trabajo se hizo la investigación del algoritmo Heap Binomial, que consta de 9 operaciones las cuales son: Make-binomial-heap(), binomial-heap-minimum(H), binomial-link(y, z), binomialheap-merge(H1, H2), binomial-heap-union(H1, H2), binomial-heap-insert(H, x), binomial-heap-extract-min(H), binomial-heap-decrease-key(H, x, k), binomial-heap-delete(H, x); desarrolladas e implementadas logrando la ejecución y experimentación de lo que el algoritmo puede hacer. Tiempo de ejecución, la cual en cada operación salió un valor, lo cual hace notar que heap binomial es mejor que el heap binario ya que en algunos casos el tipo de operación que ejecuta es mejor que el del heap binario. PALABRAS CLAVE: Heap binomial, árbol binomial, make, merge. 1. INTRODUCCIÓN El presente trabajo es el resultado de un estudio minucioso acerca del funcionamiento del heap binomial el cual se componen de un bosque de arboles binomiales. Estos se definen recursivamente y aparecen 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 esta dosado a la raíz del otro como 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 es menor 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 el tiempo 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.

2. CONTENIDO HEAP BINOMIAL - Un montículo binomial es una colección de árboles Binomiales - Árbol binomial, Bk, se define recursivamente: o B0 es un solo nodo o Bk consiste en dos árboles binomiales Bk-1 enlazados de la siguiente forma: la raíz de uno es el hijo más a la izquierda de la raíz del otro.

1

UNIVERSIDAD NACIONAL DE TRUJILLO FACULTAD DE CIENCIAS FISICAS Y MATEMATICAS ESCUELA DE INFORMATICA

-

-

BINOMIAL HEAP Profesor: Jorge Luis Guevara Díaz

Propiedades del árbol binomial Bk: k o tiene 2 nodos; o su altura es k; o tiene nodos en el nivel i, para i = 0, 1, …, k; o 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 propiedades, por inducción: o Se cumplen para B0. o Suponer que se cumplen para Bk-1: k-1 k-1 k o Bk consiste en dos copias de Bk-1, luego Bk tiene 2 + 2 = 2 nodos. o Por construcción de Bk, su altura incrementa en 1 la de Bk-1. o Sea D (k, i) el nº de nodos de Bk en el nivel i. Por construcción de Bk,

o o

El único nodo con grado mayor en Bk que en Bk-1 es la raíz, que tiene un hijo más que en Bk-1. Como la raíz de Bk-1 tiene grado k –1, la de Bk tiene grado k. Por último, por hipótesis de inducción los hijos de la raíz de B k-1 son, de izquierda a derecha, las raíces de Bk-2, Bk-3,…, B0. Por tanto, cuando se enlaza Bk-1 a Bk-1, los hijos de la raíz resultante son las raíces de Bk-1, Bk-2,…, B0.

-

Corolario: el grado máximo de cualquier nodo en un árbol binomial de n nodos es log n. o Demostración se sigue de las propiedades 1ª y 4ª

-

Montículo binomial: o Es un conjunto de árboles binomiales tales que:  Cada árbol binomial es un árbol parcialmente ordenado, es decir, la clave de todo nodo es mayor o igual que la de su padre.  Contiene no más de un árbol binomial Bi para cada grado i. Propiedad (consecuencia de la definición): o Todo montículo binomial M de n nodos consta de, como mucho, ⎣log n⎦ + 1 árboles binomiales. o Demostración: la representación binaria de n tiene ⎣log n⎦ + 1 bits, 〈b ⎣log n⎦, b ⎣log n⎦ -1,…, b0〉, de forma que

-

Como Bi tiene 2i nodos, Bi aparece en M si y sólo si bi = 1.

2

UNIVERSIDAD NACIONAL DE TRUJILLO FACULTAD DE CIENCIAS FISICAS Y MATEMATICAS ESCUELA DE INFORMATICA

-

BINOMIAL HEAP Profesor: Jorge Luis Guevara Díaz

Un ejemplo de montículo binomial de 13 nodos:

o

La representación binaria de 13 es 〈1, 1, 0, 1〉, por tanto M contiene los árboles binomiales B3, B2 y B0, con 8, 4 y 1 nodos, respectivamente.

ALGORITMO -

Tiempo de ejecución:

o Make-Binomial-Heap() head[H] = NIL return H

return if head[H1] = b then b = a a = head[H1] while b <> NIL do if sibling[a] = NIL then sibling[a] = b return else if degree[sibling[a]] < degree[b] then a = sibling[a] else c = sibling[b] sibling[b] = sibling[a] sibling[a] = b a = sibling[a] b=c

o Binomial-Heap-Minimum(H) y := NIL x := head[H] min := infinity while x <> NIL do if key[x] < min then min := key[x] y := x x := sibling[x] return y o Binomial-Link(y,z) p[y] := z sibling[y] := child[z] child[z] := y degree[z] := degree[z] + 1

o Binomial-Heap-Union(H1,H2) H := Make-Binomial-Heap() head[H] := Binomial-Heap-Merge(H1,H2) free the objects H1 and H2 but not the lists they point to if head[H] = NIL then return H prev-x := NIL x := head[H] next-x := sibling[x]

o Binomial-HeapMerge(H1,H2) a = head[H1] b = head[H2] head[H1] = Min-Degree(a, b) if head[H1] = NIL

3

UNIVERSIDAD NACIONAL DE TRUJILLO FACULTAD DE CIENCIAS FISICAS Y MATEMATICAS ESCUELA DE INFORMATICA

BINOMIAL HEAP Profesor: Jorge Luis Guevara Díaz

o Binomial-Heap-Extract-Min(H) find the root x with the minimum key in the root list of H, and remove x from the root list of H H' := Make-Binomial-Heap() reverse the order of the linked list of x's children and set head[H'] to point to the head of the resulting list H := Binomial-Heap-Union(H,H') return x

while next-x <> NIL do if (degree[x] <> degree[next-x]) or (sibling[next-x] <> NIL and degree[sibling[next-x]] = degree[x]) then prev-x := x x := next-x else if key[x] <= key[next-x] then sibling[x] := sibling[next-x] Binomial-Link(next-x,x) else if prev-x = NIL then head[H] = next-x else sibling[prev-x] := next-x Binomial-Link(x,next-x) x := next-x next-x := sibling[x] return H

o Binomial-Heap-Decrease-Key(H,x,k) if k > key[x] then error "hew key is greater than current key" key[x] := k y := x z := p[y] while z <> NIL and key[y] < key[z] do exchange key[y] and key[z] if y and z have satellite fields, exchange them, too. y := z z := p[y]

o Binomial-Heap-Insert(H,x) H' := Make-Binomial-Heap() p[x] := NIL child[x] := NIL sibling[x] := NIL degree[x] := 0 head [H'] := x H := Binomial-Heap-Union(H,H')

o Binomial-Heap-Delete(H,x) Binomial-Heap-Decrease-Key(H,x,-infinity) Binomial-Heap-Extract-Min(H)

4

UNIVERSIDAD NACIONAL DE TRUJILLO FACULTAD DE CIENCIAS FISICAS Y MATEMATICAS ESCUELA DE INFORMATICA

-

BINOMIAL HEAP Profesor: Jorge Luis Guevara Díaz

Invariante de Bucle (Correctitud del Algoritmo): o El bucle principal de todo el algoritmo es el que se encuentra en la función Binomial-Heap-Union (H1, H2). o El invariante de bucle seria: Degree[x] ≤ degree [next-x] o Que se cumple antes, durante, y al finalizar el bucle principal.

3.

REFERENCIAS Linkografia http://www.cse.yorku.ca/~aaw/Sotirios/BinomialHeapAlgorithm.html http://jc-info.blogspot.com/search/label/C%2FC%2B%2B http://es.wikibooks.org/wiki/Estructuras_de_datos_din%C3%A1micas/Colas_de_prioridad_y_montones http://www.cse.yorku.ca/~aaw/Sotirios/BinomialHeap.html Thomas H. Cormen, “Introduction to Algorithms”, Segunda edición, pp. 388 – 405, 2001

5