Montícul de Fibonacci

En Informàtica, un Montícul de Fibonacci (o Heap de Fibonacci) és una estructura de senyes subconjunt dels montículs, que a la seua volta, són un subconjunt especial dins dels boscs d'arbres. Resulta similar a un montícul binomial, pero dispon d'una millor relació entre el cost i la seua amortisació. Els montículs de Fibonacci varen ser desenrollats en 1984 per Michael L. Fredman i Robert E. Tarjan i publicats per primera volta en una revista científica en 1987. El nom de montículs de Fibonacci ve de la successió de Fibonacci, que s'usa en proves comparatives de temps (Benchmarking).

En particular, les operacions Insertar, Trobar el mínim, Decrementar la clau, i l'Unió treballen en temps constant amortisat. Les operacions Borrar i Borrar el mínim tenen un cost O(log n) com a cost amortisat. Açò significa que, escomençant en una estructura de senyes buida, qualsevol seqüència de a operacions del primer grup i b operacions del segon grup tardarien O(a + b log n). En un montícul binomial qualsevol seqüència d'operacions tardarien O((a + b)log (n)). Un montícul de Fibonacci és millor que un montícul binomial quan b és asintóticamente més chicotet que a.

El montícul de Fibonacci pot ser utilisat per a millorar el temps d'eixecució asintòtic del algoritme de Dijkstra per a calcular el camí més curt en un grafo i l'algoritme de Prim per a calcular l'arbre mínim d'un grafo.

Estructura d'un Montícul de Fibonacci

Figura 1. Eixemple d'un montícul de Fibonacci. Té tres arbres de graus 0, 1 i 3. Tres vèrtiços estan marcats (mostrats en blau). Per lo tant, el potencial de la pila és de 9.

Un Heap de Fibonacci és una colecció d'arbres que satisfan la propietat de l'orde mínim del montícul (que per a abreviar se sol utilisar l'anglicisme "Min-Heap"), és dir, a grans traces, la clau d'un fill és sempre major o igual que la del seu pare. Açò implica que la clau mínima està sempre en la raïl. Comparat en els montículs binomiales, l'estructura d'un montícul de Fibonacci és més flexible. Els arbres no tenen una forma predefinida i en un cas extrem el heap pot tindre cada element en un arbre separat o en un únic arbre de profunditat n. Esta flexibilitat permet que algunes operacions puguen ser eixecutades d'una manera "pereosa", posponent el treball per a operacions posteriors. Per eixemple, l'unió de dos montículs es fa simplement concatenant les dos llistes d'arbres, i l'operació Decrementar Clau a voltes talla un nodo del seu pare i forma un nou arbre.

No obstant, es deu introduir algun orde per a conseguir el temps d'eixecució desijat. En concret, el grau dels nodos(el número de fills) es té que mantindre baix: cada nodo té un grau màxim de O(log n) i la talla d'un subárbol la raïl del qual té grau k és per lo manco F_k + 2 , a on F_k és un número de Fibonacci. Açò es conseguix en la regla de que podem tallar com molt un fill de cada nodo no raïl. Quan és tallat un segon fill, el nodo també necessita ser tallat del seu pare i es convertix en la raïl d'un nou arbre. El número d'arbres es decrementa en l'operació Borrar mínim, a on els arbres estan units entre sí.

Com a resultat d'esta estructura, algunes operacions poden dur molt temps mentres que unes atres es fan molt corrents. En l'anàlisis del cost d'eixecució amortisat pretenem que les operacions molt ràpides tarden una miqueta més de lo que tarden. Este temps extra es resta despuix al temps d'eixecució d'operacions més llentes. La cantitat de temps aforrada per a un us posterior és medida per una funció potencial. Esta funció és:

Potencial = t + 2m

A on t és el número d'arbres en el montícul de Fibonacci, i m és el número de nodos marcats. Un nodo està marcat si a lo manco un dels seus fills es va tallar des de que el nodo es va ser fet fill d'un atre nodo (totes les raïls estan desmarcades).

Ademés, la raïl de cada arbre en un montícul té una unitat de temps almagasenada. Esta unitat de temps pot ser usada més vesprada per a unir este arbre a un atre en cost amortisat 0. Cada nodo marcat també té dos unitats de temps almagasenades. Una pot ser usada per a tallar el nodo del seu pare. Si açò succeïx, el nodo es convertix en una raïl i la segona unitat de temps es mantindrà almagasenada com en qualsevol atra raïl.

Implementació d'operacions

Per a permetre un Borrat i Concatenat ràpit, les raïls de tots els arbres estan unides una llista de tipo circular doblement enllaçada. Els fills de cada nodo també estan units usant una llista. Per a cada nodo, guardem el número de fills i si està marcat. Ademés guardem un punter a la raïl que conté la clau mínima.

L'operació Trobar Mínim és trivial perque guardem la busca al nodo que ho conté. Açò no canvia el Potencial del Montícul, ya que el cost actual i amortisat és constant. Tal com s'indica dalt, la Unió s'implementa simplement concatenant les llistes de raïls d'arbres dels dos Heaps. Açò es pot fer en temps constant i no canvia la seua Potència, resultant una atra volta un temps constant amortisat. L'operació Insertar treballa creant un nou montícul en un element i fent l'Unió. Açò es fa en temps constant, i el Potencial s'incrementa en 1, ya que el número d'arbres aumenta. El temps amortisat és constant igualment.

El montícul de Fibonacci de la figura 1 despuix de la primera fase d'extracció mínima. El nodo en clau 1 (el mínim) s'ha eliminat i els seus fills han format arbres per separat.

L'operació Extraure Mínim (lo mateix que Borrar Mínim) opera en tres fases. Primer agarrem la raïl en l'element mínim i la borrem. Els seus fills es convertiran en raïls de nous arbres. Si el número de fills era d, du un temps O(d) processar totes les noves raïls i el Potencial s'incrementa en d-1. El temps d'eixecució amortisat en esta fase és O(d) = O(log n).

El montícul de Fibonacci de la figura 1 despuix d'extraure el mínim. En primer lloc, els nodos 3 i 6 estan units entre sí. Llavors el resultat es vincula en arbres arraïlats en el nodo 2. Per últim, el nou mínim es troba.

No obstant, per a completar l'extracció del mínim, necessitem actualisar la busca a la raïl en la clau mínima. El problema és que hi ha n raïls que comprovar. En la segona fase decrementamos el número de raïls agrupant successivament les raïls del mateix grau. Quan dos raïls o i v tenen el mateix grau, fem que una d'elles siga filla de l'atra de manera que la que tinga la clau menor seguixca sent la raïl. El seu grau s'incrementarà en un. Açò es repetix fins que totes les raïls tenen un grau diferent. Per a trobar arbres del mateix grau eficientemente usem un vector de llongitut O(log n) en el que guardem una busca a una raïl de cada grau. Quan una segona raïl en el mateix grau és trobada, les dos s'unixen i s'actualisa el vector. El temps d'eixecució actual és O(log n + m) a on m és el número de raïls al principi de la segona fase. Al final tindrem com a molt O(log n) raïls (perque cada una té grau diferent). Aixina que el Potencial es decrementa a lo manco m - O(log n) i el temps d'eixecució amortisat és O(log n).

En la tercera fase, comprovem cada una de les raïls restants i trobem el mínim. Açò costera O(log n) i el potencial no canvia. El temps mig d'eixecució amortisat per a extraure el mínim és per tant O(log n).

El montícul de Fibonacci de la figura 1 despuix de la disminució dels principals nodos de 9 a 0. Este nodo, aixina com els seus dos antecessors marcats es tallen de l'arbre arrelat en l'1 i es coloquen com a noves raïls.

L'operació Decrementar Clau agarrarà el nodo, decrementará la clau i es viola la propietat del montícul (la nova clau és més chicoteta que la clau del pare), el nodo es talla del seu pare. Si el pare no és una raïl, es marca. Si ya estava marcat, es talla també i el seu pare es marca. Continuem pujant fins que, o be alcancem la raïl o un vèrtiç no marcat. En el procés vàrem crear un número k de nous arbres. El Potencial es reduïx en a lo manco k − 2. El temps per a realisar el tall és O(k) i el temps d'eixecució amortisat és constant.

Per últim, l'operació Borrar pot ser implementada simplement decrementando la clau de l'element a borrar a menys infinit, convertint-ho en el mínim de tot el montícul, llavors cridem a Extraure Mínim per a borrar-ho. El temps d'eixecució amortisat d'esta operació és O(log n).

Referències

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, Geòrgia, United States, January 28 - 30, 1996). Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, 52-58.

Vore també

1. Fibonacci (Leonardo de Pisa)