Fibonacci heaps

racias

2009 Universidad Nacional de Trujillo

Técnicas de Construcción de Programas
Profesor: Jorge Guevara Díaz

Otiniano Sáenz, Kathia Pinto Gozzer, Marie France Pérez Rivera, Jimmy Manuel Vasquez Vigo, Junior Aurelio

[FIBONACCI HEAPS]

FIBONACCI HEAPS
En Informática, un Heap de Fibonacci es una estructura de datos, subconjunto de los heaps, que a su vez, son un subconjuntoespecial dentro de los bosques de árboles. Los heaps de Fibonacci fueron desarrollados en 1984 por Michael L. Fredman y Robert E. Tarjan y publicados por primera vez en una revista científica en 1987. El nombre de heaps de Fibonacci viene de la sucesión de Fibonacci, que se usa en pruebas comparativas de tiempo. El heap de Fibonacci puede ser utilizado para mejorar el tiempo de ejecución asintótico delalgoritmo de Dijkstra, para calcular el camino más corto en un grafo y el algoritmo de Prim para calcular el árbol mínimo de un grafo. Resulta similar a un heap binomial, ya que consta de las mismas operaciones, como son INSERTAR, EXTRAER-MIN, UNION, DECREMENTAR-KEY y BORRAR; las cuales son realizadas por el Heap Binomial en tiempo de ejecución O(Lg n); la diferencia con el Heap Fibonacci es que,si una de estas operaciones no precisa eliminar un elemento, su tiempo de ejecución es O(1). Un Heap Fibonacci es un conjunto de árboles Min-Heap ordenados.

Especificaciones
Los Heaps con los que trabajaremos serán Listas Circulares Doblemente Enlazadas, para un acceso más rápido a Memoria. La estructura de cada nodo será: REGISTRO : Nodo :: Entero Clave Entero Grado Nodo *Padre Nodo **HijosNodo *Hermano_Derecho Nodo *Hermano_Izquierdo Booleano Marcado

Y la estructura de un Heap H será: REGISTRO : Heap :: Nodo * min[H] Entero n[H]

Para accesar a un Heap H, nos referiremos a él como min[H], siendo éste su nodo con clave mínima. Si min[H]=NULL, significará que el heap está vacío. La Lista Raíz es aquella lista circular doblemente enlazada, donde se encuentren todos los nodos queno tengan Padre. El número de nodos contenidos en la Lista Raíz estará dado por t[H]. El número de nodos de los heaps, será denotado como n[H]. La cantidad de nodos marcados, a los que describiremos más adelante, estará dada por m[H]. La altura de un Heap, llamada también el máximo grado será D[H].

Función Potencial
Se utiliza para analizar el tiempo de ejecución de las operaciones del HeapFibonacci. Está dada por la siguiente expresión:

Potencial = t[H] + 2m[H] > 0
El potencial de un conjunto de Heaps Fibonacci es la suma de los potenciales de cada uno de los Heaps constituyentes. Como asumiremos que en un principio, el Heap está vació, entonces su potencial será cero (0).

Operaciones
Nodo *Crear-Heap( ) Insertar(Entero dato, Nodo *H) Nodo *Minimo(Nodo *H) Nodo * Union (Nodo*H1, Nodo *H2)

Nodo * Extraer-Minimo(Nodo *H)

A continuación, desarrollaremos estas operaciones, con sus respectivos análisis. Crear Un Heap 1. Nodo *Crear-Heap( ) 2. Entero N[H]=0 3. Nodo *min[H]=NULL 4. retornar min[H] Como vemos, el tiempo de ejecución del procedimiento es O(1).

Insertar un Nodo en un Heap Insertar(Entero dato, Nodo *H) 1. Nodo X 2. X.Grado 3. X.Padre 4. X.Hijos 0NULL NULL X X

5. X.Hermano_Derecho 6. X.Hermano_Izquierdo 7. X.marcado FALSO

8. Concatenar la Lista Raíz que contiene a X con la Lista Raiz de H. 9. Si (min[H]=NULL) o (X.Clave < min[H].Clave) 10. Min[H] 11. n[H] X n[H]+1

En las líneas 2-7, inicializamos los campos de la estructura del Nodo X, apuntándose a sí mismo, por ser una lista circular doblemente enlazada. En la línea 8, agregamos Xa la lista raíz de H, haciéndose esto en O(1). En las líneas 9-10, actualizamos min[H], si fuera necesario. Finalmente, en la línea 11, incrementamos el n[H]. Para determinar el Costo de Ejecución de Insertar, hagamos que H sea el Heap Fibonaci de entrada y que H’ sea H con el nuevo nodo insertado. Entonces: t(H′) = t[H]+1

m(H′) = m[H] Así mismo, el potencial, incrementará en:

∆Potencial...