fbpx
Wikipedia

Montículo de Fibonacci

En Informática, un Montículo de Fibonacci (o Heap de Fibonacci) es una estructura de datos subconjunto de los montículos, que a su vez, son un subconjunto especial dentro de los bosques de árboles. Resulta similar a un montículo binomial, pero dispone de una mejor relación entre el coste y su amortización. Los montículos 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 montículos de Fibonacci viene de la sucesión de Fibonacci, que se usa en pruebas comparativas de tiempo (Benchmarking).

En particular, las operaciones Insertar, Encontrar el mínimo, Decrementar la clave, y la Unión trabajan con tiempo constante amortizado. Las operaciones Borrar y Borrar el mínimo tienen un coste O(log n) 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 log n). En un montículo binomial cualquier secuencia de operaciones tardarían O((a + b)log (n)). Un montículo de Fibonacci es mejor que un montículo binomial cuando b es asintóticamente más pequeño que a.

El montículo de Fibonacci puede ser utilizado 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.

Estructura de un Montículo de Fibonacci

 
Figura 1. Ejemplo de un montículo de Fibonacci. Tiene tres árboles de grados 0, 1 y 3. Tres vértices están marcados (mostrados en azul). Por lo tanto, el potencial de la pila es de 9.

Un Heap de Fibonacci es una colección de árboles que satisfacen la propiedad del orden mínimo del montículo (que para abreviar se suele utilizar el anglicismo "Min-Heap"), es decir, a grandes rasgos, la clave de un hijo es siempre mayor o igual que la de su padre. Esto implica que la clave mínima está siempre en la raíz. Comparado con los montículos binomiales, la estructura de un montículo de Fibonacci es más flexible. Los árboles no tienen una forma predefinida y en un caso extremo el heap puede tener cada elemento en un árbol separado o en un único árbol de profundidad n. Esta flexibilidad permite que algunas operaciones puedan ser ejecutadas de una manera "perezosa", posponiendo el trabajo para operaciones posteriores. Por ejemplo, la unión de dos montículos se hace simplemente concatenando las dos listas de árboles, y la operación Decrementar Clave a veces corta un nodo de su padre y forma un nuevo árbol.

Sin embargo, se debe introducir algún orden para conseguir el tiempo de ejecución deseado. En concreto, el grado de los nodos(el número de hijos) se tiene que mantener bajo: cada nodo tiene un grado máximo de O(log n) y la talla de un subárbol cuya raíz tiene grado k es por lo menos Fk + 2 , donde Fk es un número de Fibonacci. Esto se consigue con la regla de que podemos cortar como mucho un hijo de cada nodo no raíz. Cuando es cortado un segundo hijo, el nodo también necesita ser cortado de su padre y se convierte en la raíz de un nuevo árbol. El número de árboles se decrementa en la operación Borrar mínimo, donde los árboles están unidos entre sí.

Como resultado de esta estructura, algunas operaciones pueden llevar mucho tiempo mientras que otras se hacen muy deprisa. En el análisis del coste de ejecución amortizado pretendemos 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 = t + 2m

Donde t es el número de árboles en el montículo 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).

Además, la raíz de cada árbol en un montículo tiene una unidad de tiempo almacenada. Esta unidad de tiempo puede ser usada más tarde para unir este árbol a otro con coste amortizado 0. Cada nodo marcado también tiene dos unidades de tiempo almacenadas. Una puede ser usada para cortar el nodo de su padre. Si esto sucede, el nodo se convierte en una raíz y la segunda unidad de tiempo se mantendrá almacenada como en cualquier otra raíz.

Implementación de operaciones

Para permitir un Borrado y Concatenado rápido, las raíces de todos los árboles están unidas una lista de tipo circular doblemente enlazada. Los hijos de cada nodo también están unidos usando una lista. Para cada nodo, guardamos el número de hijos y si está marcado. Además guardamos un puntero a la raíz que contiene la clave mínima.

La operación Encontrar Mínimo es trivial porque guardamos el puntero al nodo que lo contiene. Esto no cambia el Potencial del Montículo, ya que el coste actual y amortizado es constante. Tal como se indica arriba, la Unión se implementa simplemente concatenando las listas de raíces de árboles de los dos Heaps. Esto se puede hacer en tiempo constante y no cambia su Potencia, resultando otra vez un tiempo constante amortizado. La operación Insertar trabaja creando un nuevo montículo con un elemento y haciendo la Unión. Esto se hace en tiempo constante, y el Potencial se incrementa en 1, ya que el número de árboles aumenta. El tiempo amortizado es constante igualmente.

 
El montículo de Fibonacci de la figura 1 después de la primera fase de extracción mínima. El nodo con clave 1 (el mínimo) se ha eliminado y sus hijos han formado árboles por separado.

La operación Extraer Mínimo (lo mismo que Borrar Mínimo) opera en tres fases. Primero cogemos la raíz con el elemento mínimo y la borramos. Sus hijos se convertirán en raíces de nuevos árboles. Si el número de hijos era d, lleva un tiempo O(d) procesar todas las nuevas raíces y el Potencial se incrementa en d-1. El tiempo de ejecución amortizado en esta fase es O(d) = O(log n).

 
El montículo de Fibonacci de la figura 1 después de extraer el mínimo. En primer lugar, los nodos 3 y 6 están unidos entre sí. Entonces el resultado se vincula con árboles arraigados en el nodo 2. Por último, el nuevo mínimo se encuentra.

Sin embargo, para completar la extracción del mínimo, necesitamos actualizar el puntero a la raíz con la clave mínima. El problema es que hay n raíces que comprobar. En la segunda fase decrementamos el número de raíces agrupando sucesivamente las raíces del mismo grado. Cuando dos raíces u y v tienen el mismo grado, hacemos que una de ellas sea hija de la otra de manera que la que tenga la clave menor siga siendo la raíz. Su grado se incrementará en uno. Esto se repite hasta que todas las raíces tienen un grado diferente. Para encontrar árboles del mismo grado eficientemente usamos un vector de longitud O(log n) en el que guardamos un puntero a una raíz de cada grado. Cuando una segunda raíz con el mismo grado es encontrada, las dos se unen y se actualiza el vector. El tiempo de ejecución actual es O(log n + m) donde m es el número de raíces al principio de la segunda fase. Al final tendremos como mucho O(log n) raíces (porque cada una tiene grado diferente). Así pues el Potencial se decrementa al menos m - O(log n) y el tiempo de ejecución amortizado es O(log n).

En la tercera fase, comprobamos cada una de las raíces restantes y encontramos el mínimo. Esto cuesta O(log n) y el potencial no cambia. El tiempo medio de ejecución amortizado para extraer el mínimo es por consiguiente O(log n).

 
El montículo de Fibonacci de la figura 1 después de la disminución de los principales nodos de 9 a 0. Este nodo, así como sus dos antecesores marcados se cortan del árbol enraizado en el 1 y se colocan como nuevas raíces.

La operación Decrementar Clave cogerá el nodo, decrementará la clave y se viola la propiedad del montículo (la nueva clave es más pequeña que la clave del padre), el nodo se corta de su padre. Si el padre no es una raíz, se marca. Si ya estaba marcado, se corta también y su padre se marca. Continuamos subiendo hasta que, o bien alcanzamos la raíz o un vértice no marcado. En el proceso creamos un número k de nuevos árboles. El Potencial se reduce en al menos k − 2. El tiempo para realizar el corte es O(k) y el tiempo de ejecución amortizado es constante.

Por último, la operación Borrar puede ser implementada simplemente decrementando la clave del elemento a borrar a menos infinito, convirtiéndolo en el mínimo de todo el montículo, entonces llamamos a Extraer Mínimo para borrarlo. El tiempo de ejecución amortizado de esta operación es O(log n).

Peor Caso

Aunque el tiempo total de ejecución de una secuencia de operaciones que empiezan por una estructura vacía viene determinado por lo explicado anteriormente, algunas, aunque muy pocas, operaciones de la secuencia pueden llevar mucho tiempo(en particular Decrementar Clave, Borrar y Borrar Mínimo tienen tiempo de ejecución lineal en el peor caso). Por este motivo los montículos de Fibonacci y otras estructuras con costes amortizados pueden no ser apropiadas para sistemas de tiempo real.

Resumen de Tiempos de Ejecución

Lista Enlazada Árbol Binario Min-Heap Montículo de Fibonacci Lista Brodal [1]
Insertar O(1) O(log n) O(log n) O(1) O(1)
Acceso Mínimo O(n) O(1) O(1) O(1) O(1)
Borrar mínimo O(n) O(log n) O(log n) O(log n)* O(log n)
Disminuir Clave O(1) O(log n) O(log n) O(1)* O(1)
Borrar O(n) O(n) O(log n) O(log n)* O(log n)
Unión O(1) O(n + m) O(m log(n+m)) O(1) O(1)

(*)Tiempo Amortizado

Referencias

  1. Fredman M. L. & Tarjan R. E. (1987). Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM 34(3), 596-615.
  2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 20: Fibonacci Heaps, pp.476–497.
  3. Brodal, G. S. 1996. Worst-case efficient priority queues. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Atlanta, Georgia, United States, January 28 - 30, 1996). Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, 52-58.

Enlaces externos

  1. Visualización de un Montículo de Fibonacci
  2. Implementación en C de un Heap de Fibonacci el 1 de julio de 2007 en Wayback Machine.
  3. Algoritmo en pseudocódigo del montículo de Fibonacci
  4. Pseudocódigo y explicación de J. Boyer (Dr. Dobb's Algorithm Alley)

Véase también

  1. Fibonacci (Leonardo de Pisa)
  •   Datos: Q1410737

montículo, fibonacci, para, otros, usos, este, término, véase, montículo, desambiguación, informática, heap, fibonacci, estructura, datos, subconjunto, montículos, subconjunto, especial, dentro, bosques, árboles, resulta, similar, montículo, binomial, pero, di. Para otros usos de este termino vease Monticulo desambiguacion En Informatica un Monticulo de Fibonacci o Heap de Fibonacci es una estructura de datos subconjunto de los monticulos que a su vez son un subconjunto especial dentro de los bosques de arboles Resulta similar a un monticulo binomial pero dispone de una mejor relacion entre el coste y su amortizacion Los monticulos de Fibonacci fueron desarrollados en 1984 por Michael L Fredman y Robert E Tarjan y publicados por primera vez en una revista cientifica en 1987 El nombre de monticulos de Fibonacci viene de la sucesion de Fibonacci que se usa en pruebas comparativas de tiempo Benchmarking En particular las operaciones Insertar Encontrar el minimo Decrementar la clave y la Union trabajan con tiempo constante amortizado Las operaciones Borrar y Borrar el minimo tienen un coste O log n como coste amortizado Esto significa que empezando con una estructura de datos vacia cualquier secuencia de a operaciones del primer grupo y b operaciones del segundo grupo tardarian O a b log n En un monticulo binomial cualquier secuencia de operaciones tardarian O a b log n Un monticulo de Fibonacci es mejor que un monticulo binomial cuando b es asintoticamente mas pequeno que a El monticulo de Fibonacci puede ser utilizado para mejorar el tiempo de ejecucion asintotico del algoritmo de Dijkstra para calcular el camino mas corto en un grafo y el algoritmo de Prim para calcular el arbol minimo de un grafo Indice 1 Estructura de un Monticulo de Fibonacci 2 Implementacion de operaciones 3 Peor Caso 4 Resumen de Tiempos de Ejecucion 5 Referencias 6 Enlaces externos 7 Vease tambienEstructura de un Monticulo de Fibonacci Editar Figura 1 Ejemplo de un monticulo de Fibonacci Tiene tres arboles de grados 0 1 y 3 Tres vertices estan marcados mostrados en azul Por lo tanto el potencial de la pila es de 9 Un Heap de Fibonacci es una coleccion de arboles que satisfacen la propiedad del orden minimo del monticulo que para abreviar se suele utilizar el anglicismo Min Heap es decir a grandes rasgos la clave de un hijo es siempre mayor o igual que la de su padre Esto implica que la clave minima esta siempre en la raiz Comparado con los monticulos binomiales la estructura de un monticulo de Fibonacci es mas flexible Los arboles no tienen una forma predefinida y en un caso extremo el heap puede tener cada elemento en un arbol separado o en un unico arbol de profundidad n Esta flexibilidad permite que algunas operaciones puedan ser ejecutadas de una manera perezosa posponiendo el trabajo para operaciones posteriores Por ejemplo la union de dos monticulos se hace simplemente concatenando las dos listas de arboles y la operacion Decrementar Clave a veces corta un nodo de su padre y forma un nuevo arbol Sin embargo se debe introducir algun orden para conseguir el tiempo de ejecucion deseado En concreto el grado de los nodos el numero de hijos se tiene que mantener bajo cada nodo tiene un grado maximo de O log n y la talla de un subarbol cuya raiz tiene grado k es por lo menos Fk 2 donde Fk es un numero de Fibonacci Esto se consigue con la regla de que podemos cortar como mucho un hijo de cada nodo no raiz Cuando es cortado un segundo hijo el nodo tambien necesita ser cortado de su padre y se convierte en la raiz de un nuevo arbol El numero de arboles se decrementa en la operacion Borrar minimo donde los arboles estan unidos entre si Como resultado de esta estructura algunas operaciones pueden llevar mucho tiempo mientras que otras se hacen muy deprisa En el analisis del coste de ejecucion amortizado pretendemos que las operaciones muy rapidas tarden un poco mas de lo que tardan Este tiempo extra se resta despues al tiempo de ejecucion de operaciones mas lentas La cantidad de tiempo ahorrada para un uso posterior es medida por una funcion potencial Esta funcion es Potencial t 2mDonde t es el numero de arboles en el monticulo de Fibonacci y m es el numero de nodos marcados Un nodo esta marcado si al menos uno de sus hijos se corto desde que el nodo se fue hecho hijo de otro nodo todas las raices estan desmarcadas Ademas la raiz de cada arbol en un monticulo tiene una unidad de tiempo almacenada Esta unidad de tiempo puede ser usada mas tarde para unir este arbol a otro con coste amortizado 0 Cada nodo marcado tambien tiene dos unidades de tiempo almacenadas Una puede ser usada para cortar el nodo de su padre Si esto sucede el nodo se convierte en una raiz y la segunda unidad de tiempo se mantendra almacenada como en cualquier otra raiz Implementacion de operaciones EditarPara permitir un Borrado y Concatenado rapido las raices de todos los arboles estan unidas una lista de tipo circular doblemente enlazada Los hijos de cada nodo tambien estan unidos usando una lista Para cada nodo guardamos el numero de hijos y si esta marcado Ademas guardamos un puntero a la raiz que contiene la clave minima La operacion Encontrar Minimo es trivial porque guardamos el puntero al nodo que lo contiene Esto no cambia el Potencial del Monticulo ya que el coste actual y amortizado es constante Tal como se indica arriba la Union se implementa simplemente concatenando las listas de raices de arboles de los dos Heaps Esto se puede hacer en tiempo constante y no cambia su Potencia resultando otra vez un tiempo constante amortizado La operacion Insertar trabaja creando un nuevo monticulo con un elemento y haciendo la Union Esto se hace en tiempo constante y el Potencial se incrementa en 1 ya que el numero de arboles aumenta El tiempo amortizado es constante igualmente El monticulo de Fibonacci de la figura 1 despues de la primera fase de extraccion minima El nodo con clave 1 el minimo se ha eliminado y sus hijos han formado arboles por separado La operacion Extraer Minimo lo mismo que Borrar Minimo opera en tres fases Primero cogemos la raiz con el elemento minimo y la borramos Sus hijos se convertiran en raices de nuevos arboles Si el numero de hijos era d lleva un tiempo O d procesar todas las nuevas raices y el Potencial se incrementa en d 1 El tiempo de ejecucion amortizado en esta fase es O d O log n El monticulo de Fibonacci de la figura 1 despues de extraer el minimo En primer lugar los nodos 3 y 6 estan unidos entre si Entonces el resultado se vincula con arboles arraigados en el nodo 2 Por ultimo el nuevo minimo se encuentra Sin embargo para completar la extraccion del minimo necesitamos actualizar el puntero a la raiz con la clave minima El problema es que hay n raices que comprobar En la segunda fase decrementamos el numero de raices agrupando sucesivamente las raices del mismo grado Cuando dos raices u y v tienen el mismo grado hacemos que una de ellas sea hija de la otra de manera que la que tenga la clave menor siga siendo la raiz Su grado se incrementara en uno Esto se repite hasta que todas las raices tienen un grado diferente Para encontrar arboles del mismo grado eficientemente usamos un vector de longitud O log n en el que guardamos un puntero a una raiz de cada grado Cuando una segunda raiz con el mismo grado es encontrada las dos se unen y se actualiza el vector El tiempo de ejecucion actual es O log n m donde m es el numero de raices al principio de la segunda fase Al final tendremos como mucho O log n raices porque cada una tiene grado diferente Asi pues el Potencial se decrementa al menos m O log n y el tiempo de ejecucion amortizado es O log n En la tercera fase comprobamos cada una de las raices restantes y encontramos el minimo Esto cuesta O log n y el potencial no cambia El tiempo medio de ejecucion amortizado para extraer el minimo es por consiguiente O log n El monticulo de Fibonacci de la figura 1 despues de la disminucion de los principales nodos de 9 a 0 Este nodo asi como sus dos antecesores marcados se cortan del arbol enraizado en el 1 y se colocan como nuevas raices La operacion Decrementar Clave cogera el nodo decrementara la clave y se viola la propiedad del monticulo la nueva clave es mas pequena que la clave del padre el nodo se corta de su padre Si el padre no es una raiz se marca Si ya estaba marcado se corta tambien y su padre se marca Continuamos subiendo hasta que o bien alcanzamos la raiz o un vertice no marcado En el proceso creamos un numero k de nuevos arboles El Potencial se reduce en al menos k 2 El tiempo para realizar el corte es O k y el tiempo de ejecucion amortizado es constante Por ultimo la operacion Borrar puede ser implementada simplemente decrementando la clave del elemento a borrar a menos infinito convirtiendolo en el minimo de todo el monticulo entonces llamamos a Extraer Minimo para borrarlo El tiempo de ejecucion amortizado de esta operacion es O log n Peor Caso EditarAunque el tiempo total de ejecucion de una secuencia de operaciones que empiezan por una estructura vacia viene determinado por lo explicado anteriormente algunas aunque muy pocas operaciones de la secuencia pueden llevar mucho tiempo en particular Decrementar Clave Borrar y Borrar Minimo tienen tiempo de ejecucion lineal en el peor caso Por este motivo los monticulos de Fibonacci y otras estructuras con costes amortizados pueden no ser apropiadas para sistemas de tiempo real Resumen de Tiempos de Ejecucion EditarLista Enlazada Arbol Binario Min Heap Monticulo de Fibonacci Lista Brodal 1 Insertar O 1 O log n O log n O 1 O 1 Acceso Minimo O n O 1 O 1 O 1 O 1 Borrar minimo O n O log n O log n O log n O log n Disminuir Clave O 1 O log n O log n O 1 O 1 Borrar O n O n O log n O log n O log n Union O 1 O n m O m log n m O 1 O 1 Tiempo AmortizadoReferencias EditarFredman M L amp Tarjan R E 1987 Fibonacci heaps and their uses in improved network optimization algorithms Journal of the ACM 34 3 596 615 Thomas H Cormen Charles E Leiserson Ronald L Rivest and Clifford Stein Introduction to Algorithms Second Edition MIT Press and McGraw Hill 2001 ISBN 0 262 03293 7 Chapter 20 Fibonacci Heaps pp 476 497 Brodal G S 1996 Worst case efficient priority queues In Proceedings of the Seventh Annual ACM SIAM Symposium on Discrete Algorithms Atlanta Georgia United States January 28 30 1996 Symposium on Discrete Algorithms Society for Industrial and Applied Mathematics Philadelphia PA 52 58 Enlaces externos EditarVisualizacion de un Monticulo de Fibonacci Implementacion en C de un Heap de Fibonacci Archivado el 1 de julio de 2007 en Wayback Machine Algoritmo en pseudocodigo del monticulo de Fibonacci Pseudocodigo y explicacion de J Boyer Dr Dobb s Algorithm Alley Vease tambien EditarFibonacci Leonardo de Pisa Datos Q1410737Obtenido de https es wikipedia org w index php title Monticulo de Fibonacci amp oldid 135198783, wikipedia, wiki, leyendo, leer, libro, biblioteca,

español

, española, descargar, gratis, descargar gratis, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, imagen, música, canción, película, libro, juego, juegos