Download Cap_7a(heaps)_2008

Heap Fibonacci
heap de Fibonacci es una estructura de datos similar a un heap
binomial pero con mejor coste amortizado.
se utiliza para mejorar el tiempo de ejecución asintótico del
algoritmo 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.
En particular, las operaciones Insertar, encontrar el mínimo,
decrementar la clave, y la unión trabajan con tiempo constante
amortizado.
Heap Fibonacci
Análisis amortizado
En general, el coste de cada operación sobre el TAD (estructura
de datos) no es independiente de las operaciones realizadas
previamente.
En lugar de caracterizar el coste (mejor, peor, medio) de
cada operación individual resulta más adecuado considerar
secuencias de operaciones arbitrarias sobre el TAD.
Es posible que una operación tenga un coste peor elevado, pero
que éste sea muy improbable cuando la operación se aplica
dentro de secuencias de operaciones válidas.
Heap Fibonacci
Análisis amortizado
Coste amortizado: coste que evalúa la eficiencia de un conjunto
de operaciones que se aplican en un mismo contexto.
El coste amortizado determina una cota superior (peor caso) para
el coste de una secuencia de operaciones.
Se dice que una operación tiene un coste amortizado t si en
cualquier secuencia de operaciones en la que aparezca, el coste
total de las operaciones dividido por el número de éstas es
menor o igual a t.
Heap Fibonacci
Análisis amortizado
El análisis amortizado difiere del análisis en el caso medio
en que no se consideran probabilidades.
El análisis amortizado garantiza la eficiencia media de
cada operación en el peor caso.
Referencia para el tema: Capítulo 17 (pag. 405)
“Introduction to Algorithms”
T.H. Cormen, C.E. Leiserson, R.L. Rivest. MIT Press, 1990.
Heap Fibonacci
Heap Fibonacci
Heap Fibonacci y Heap Binomial son una colección de heap
ordenados.
Propiedades:
• Nodos en FH no están ordenados (por grado) en la lista de raíz
o como hermanos.
•Raíz y hermanos están dispuestos en una lista enlazada circular.
•Cada nodo almacena su grado (nº de hijos).
•Min(H) es un puntero al mínimo raíz en la lista de raíz.
•N(H) es el nº de nodos actualmente en H.
Heap Fibonacci
Heap Fibonacci
Sea A un árbol con raíz min(H),
extrae A desde H.
Elimina la raíz de A; reinserta el resto de los árboles
“abandonados”en la lista raíz del heap, actualiza min(H)
durante este proceso.
Une raíz de igual grado hasta que al menos una raíz restante
de cada grado.
Heap Fibonacci
Crea un nuevo árbol que contiene x y lo agrega a la lista de raíz.
Y actualiza punteros adecuadamente.
Heap Fibonacci
Heap Fibonacci
Las operaciones Borrar y Borrar el mínimo tienen un coste
O(logn) como coste amortizado. Esto significa que, empezando
con una estructura de datos vacía, cualquier secuencia de ‘a’
operaciones del primer grupo y ‘b’ operaciones del segundo
grupo tardarían O(a + b.logn).
En un heap ‘binomial’ esta secuencia de operaciones tardarían
O((a+b)log(n)). Un heap de Fibonacci es mejor que un heap
binomial cuando b es asintóticamente más pequeño que a.
Aunque los costes son los arriba indicados, algunas operaciones
pueden llevar mucho tiempo (en concreto Decrementar clave,
Borrar y Borrar mínimo tienen un coste lineal en el peor caso).
Por esta razón los Heaps de Fibonacci y otras estructuras de
datos con coste amortizado no son apropiadas para sistemas de
tiempo real.
Heap Fibonacci
Como resultado, algunas operaciones pueden llevar mucho
tiempo mientras que otras se hacen muy deprisa. En el análisis
del coste de ejecución amortizado se pretende que las
operaciones muy rápidas tarden un poco más de lo que tardan.
Este tiempo extra se resta después al tiempo de ejecución de
operaciones más lentas. La cantidad de tiempo ahorrada para un
uso posterior es medida por una función potencial. Esta función
es:
Potencial (H)= t (H)+ 2m(H)
Donde t es el número de árboles en el Heap de Fibonacci, y m es
el número de nodos marcados. Un nodo está marcado si al
menos uno de sus hijos se cortó desde que el nodo se fue hecho
hijo de otro nodo (todas las raíces están desmarcadas).
Heap Fibonacci
Sea A un árbol con raíz min(H),
extrae A desde H.
Elimina la raíz de A; reinserta el resto de los árboles
“abandonados”en la lista raíz del heap, actualiza min(H)
durante este proceso.
Une raíz de igual grado hasta que al menos una raíz restante
de cada grado.
Heap Fibonacci
Heap Fibonacci
Heap Fibonacci
Heap Fibonacci