In der Informatik ist ein Haufen von Fibonacci eine Haufen-Datenstruktur, die aus einer Sammlung von Bäumen besteht. Es hat eine bessere amortisierte Laufzeit als ein binomischer Haufen. Haufen von Fibonacci wurden von Michael L. Fredman und Robert E. Tarjan 1984 entwickelt und zuerst in einer wissenschaftlichen Zeitschrift 1987 veröffentlicht. Der Name des Haufens von Fibonacci kommt aus Fibonacci-Zahlen, die in der Laufzeit-Analyse verwendet werden.

Finden-Minimum ist O (1) amortisierte Zeit. Operationseinsatz, Abnahme-Schlüssel und Verflechtung (Vereinigung) Arbeit in der unveränderlichen amortisierten Zeit.. Operationen löschen und löschen minimale Arbeit in O (loggen Sie n) amortisierte Zeit. Das bedeutet, dass, von einer leeren Datenstruktur, jeder Folge anfangend, Operationen von der ersten Gruppe und b Operationen von der zweiten Gruppe O nehmen würden (+ b, loggen n) Zeit. In einem binomischen Haufen würde solch eine Folge von Operationen O ((+ b) Klotz (n)) Zeit nehmen. Ein Fibonacci Haufen ist so besser als ein binomischer Haufen, wenn b asymptotisch kleiner ist als a.

Das Verwenden von Fibonacci Haufen nach Vorzugswarteschlangen verbessert die asymptotische Laufzeit von wichtigen Algorithmen wie der Algorithmus von Dijkstra, für den kürzesten Pfad zwischen zwei Knoten in einem Graphen zu schätzen.

Struktur

Ein Fibonacci Haufen ist eine Sammlung von Bäumen, die das Eigentum des minimalen Haufens befriedigen, d. h. der Schlüssel eines Kindes ist immer größer oder gleich dem Schlüssel des Elternteils. Das deutet an, dass der minimale Schlüssel immer an der Wurzel von einem der Bäume ist. Im Vergleich zu binomischen Haufen ist die Struktur eines Haufens von Fibonacci flexibler. Die Bäume haben keine vorgeschriebene Gestalt, und im äußersten Fall kann der Haufen jedes Element in einem getrennten Baum haben. Diese Flexibilität erlaubt einigen Operationen, auf eine "faule" Weise durchgeführt zu werden, die Arbeit für spätere Operationen verschiebend. Zum Beispiel das Mischen von Haufen wird einfach durch das Verketten der zwei Listen von Bäumen getan, und Operationsabnahme-Schlüssel schneidet manchmal einen Knoten von seinem Elternteil und bildet einen neuen Baum.

Jedoch an einem Punkt muss eine Ordnung in den Haufen eingeführt werden, um die gewünschte Laufzeit zu erreichen. Insbesondere Grade von Knoten (hier bedeutet Grad die Zahl von Kindern), werden ziemlich niedrig behalten: Jeder Knoten hat Grad am grössten Teil von O (loggen Sie n), und die Größe eines Subbaums, der in einem Knoten des Grads k eingewurzelt ist, ist mindestens F, wo F die kth Fibonacci-Zahl ist. Das wird durch die Regel erreicht, dass wir höchstens ein Kind jedes Nichtwurzelknotens schneiden können. Wenn ein zweites Kind geschnitten wird, muss der Knoten selbst von seinem Elternteil geschnitten werden und wird die Wurzel eines neuen Baums (sieh Beweis von Grad-Grenzen, unten). Die Anzahl von Bäumen wird in der Operation reduziert löschen Minimum, wo Bäume zusammen verbunden werden.

Infolge einer entspannten Struktur können einige Operationen viel Zeit in Anspruch nehmen, während andere sehr schnell getan werden. In der amortisierten Laufzeit-Analyse geben wir vor, dass sehr schnelle Operationen ein kleines bisschen länger nehmen, als sie wirklich tun. Diese zusätzliche Zeit wird dann später von der wirklichen Laufzeit von langsamen Operationen abgezogen. Die für den späteren Gebrauch gesparte Zeitdauer wird in jedem gegebenen Moment durch eine potenzielle Funktion gemessen. Das Potenzial eines Haufens von Fibonacci wird durch gegeben

:Potential = t + 2 M

wo t die Zahl von Bäumen im Haufen von Fibonacci ist, und M die Zahl von gekennzeichneten Knoten ist. Ein Knoten wird gekennzeichnet, wenn mindestens ein seiner Kinder geschnitten wurden, seitdem dieser Knoten ein Kind eines anderen Knotens gemacht wurde (alle Wurzeln sind nicht markiert).

So hat die Wurzel jedes Baums in einem Haufen eine Einheit der versorgten Zeit. Diese Einheit der Zeit kann später verwendet werden, um diesen Baum mit einem anderen Baum in der amortisierten Zeit 0 zu verbinden. Außerdem hat jeder gekennzeichnete Knoten zwei Einheiten der versorgten Zeit. Einer kann verwendet werden, um den Knoten von seinem Elternteil zu schneiden. Wenn das geschieht, wird der Knoten eine Wurzel, und die zweite Einheit der Zeit wird versorgt darin als in jeder anderen Wurzel bleiben.

Durchführung von Operationen

Um schnelles Auswischen und Verkettung zu erlauben, werden die Wurzeln aller Bäume mit einem Rundschreiben verbunden, doppelt hat Liste verbunden. Die Kinder jedes Knotens werden auch mit solch einer Liste verbunden. Für jeden Knoten erhalten wir seine Zahl von Kindern aufrecht, und ob der Knoten gekennzeichnet wird. Außerdem erhalten wir einen Zeigestock zur Wurzel aufrecht, die den minimalen Schlüssel enthält.

Operation findet minimal ist jetzt trivial, weil wir den Zeigestock zum Knoten behalten, der sie enthält. Es ändert das Potenzial des Haufens nicht, deshalb sowohl wirklich als auch amortisiert kosten ist unveränderlich. Wie oben erwähnt wird Verflechtung einfach durch das Verketten der Listen von Baumwurzeln der zwei Haufen durchgeführt. Das kann in der unveränderlichen Zeit getan werden, und das Potenzial ändert sich nicht, wieder zur unveränderlichen amortisierten Zeit führend.

Operationseinsatz arbeitet durch das Schaffen eines neuen Haufens mit einem Element und das Tun der Verflechtung. Das, nimmt und die potenziellen Zunahmen durch eine Zeit in Anspruch, weil die Zahl von Bäumen zunimmt. Die amortisierten Kosten sind so noch unveränderlich.

Operationsextrakt-Minimum (dasselbe, wie Minimum löschen) funktioniert in drei Phasen. Zuerst nehmen wir die Wurzel, die das minimale Element enthält, und entfernen es. Seine Kinder werden Wurzeln von neuen Bäumen werden. Wenn die Zahl von Kindern d war, nimmt sie O (d) Zeit in Anspruch, um alle neuen Wurzeln und die potenziellen Zunahmen durch d1 zu bearbeiten. Deshalb ist die amortisierte Laufzeit dieser Phase O (d) = O (loggen Sie n).

Jedoch, um die Extrakt-Minimum-Operation zu vollenden, müssen wir den Zeigestock zur Wurzel mit dem minimalen Schlüssel aktualisieren. Leider kann es bis zu N-Wurzeln geben, die wir überprüfen müssen. In der zweiten Phase reduzieren wir deshalb die Anzahl gegen Wurzeln, indem wir zusammen Wurzeln desselben Grads nacheinander verbinden. Wenn zwei Wurzeln u und v denselben Grad haben, machen wir einen von ihnen ein Kind vom anderen, so dass derjenige mit dem kleineren Schlüssel die Wurzel bleibt. Sein Grad wird durch einen zunehmen. Das wird wiederholt, bis jede Wurzel einen verschiedenen Grad hat. Um Bäume desselben Grads effizient zu finden, verwenden wir eine Reihe der Länge O (loggen Sie n), in dem wir einen Zeigestock zu einer Wurzel jedes Grads behalten. Wenn eine zweite Wurzel desselben Grads gefunden wird, werden die zwei verbunden, und die Reihe wird aktualisiert. Die wirkliche Laufzeit ist O (loggen Sie n + m), wo M die Zahl von Wurzeln am Anfang der zweiten Phase ist. Am Ende werden wir am grössten Teil von O haben (loggen Sie n), Wurzeln (weil jeder einen verschiedenen Grad hat). Deshalb der Unterschied in der potenziellen Funktion aus der Zeit vor dieser Phase dazu, nachdem es ist: O (loggen n),  M und die amortisierte Laufzeit ist dann am grössten Teil von O (loggen Sie n + m) + O (loggen n),  M = O (loggen n). Da wir die Einheiten des Potenzials hoch schrauben können, das an der Einfügung in jedem Knoten durch den unveränderlichen Faktor im O (m) ein Teil der Ist-Kosten für diese Phase versorgt ist.

In der dritten Phase überprüfen wir jede der restlichen Wurzeln und finden das Minimum. Das nimmt O (loggen Sie n) Zeit und das Potenzial ändern sich nicht. Die gesamte amortisierte Laufzeit des Extrakt-Minimums ist deshalb O (loggen Sie n).

Operationsabnahme-Schlüssel wird den Knoten nehmen, den Schlüssel vermindern, und wenn das Haufen-Eigentum verletzt wird (der neue Schlüssel ist kleiner als der Schlüssel des Elternteils), der Knoten wird von seinem Elternteil geschnitten. Wenn der Elternteil nicht eine Wurzel ist, wird sie gekennzeichnet. Wenn es bereits gekennzeichnet worden ist, wird es ebenso geschnitten, und sein Elternteil wird gekennzeichnet. Wir machen aufwärts weiter, bis wir entweder die Wurzel oder einen nicht markierten Knoten erreichen. Im Prozess schaffen wir eine Zahl sagen wir k neuer Bäume. Jeder dieser neuen Bäume außer vielleicht dem ersten wurde ursprünglich gekennzeichnet, aber als eine Wurzel wird es nicht markiert werden. Ein Knoten kann gekennzeichnet werden. Deshalb nimmt das Potenzial durch mindestens k &minus ab; 2. Die wirkliche Zeit, um den Ausschnitt durchzuführen, war O (k), deshalb ist die amortisierte Laufzeit unveränderlich.

Schließlich, Operation löschen kann einfach durch das Verringern des Schlüssels des Elements durchgeführt werden, das zu minus die Unendlichkeit zu löschen ist, so es ins Minimum des ganzen Haufens verwandelnd. Dann nennen wir Extrakt-Minimum, um es zu entfernen. Die amortisierte Laufzeit dieser Operation ist O (loggen Sie n).

Beweis von Grad-Grenzen

Die amortisierte Leistung eines Haufens von Fibonacci hängt vom Grad ab (Zahl von Kindern) jeder Baumwurzel, die O ist (loggen Sie n), wo n die Größe des Haufens ist. Hier zeigen wir, dass die Größe (U-Boot) Baum, der an jedem Knoten x des Grads d im Haufen eingewurzelt ist, muss Größe mindestens F haben, wo F die kth Fibonacci-Zahl ist. Der gebundene Grad folgt daraus und der Tatsache (leicht bewiesen durch die Induktion) das für alle ganzen Zahlen, wo. (Wir haben dann, und das Bringen des Klotzes zur Basis von beiden Seiten, gibt wie erforderlich.)

Ziehen Sie in Betracht jeder Knoten x irgendwo im Haufen (x braucht nicht die Wurzel von einem der Hauptbäume zu sein). Definieren Sie Größe (x), um die Größe des Baums zu sein, der an x (die Zahl von Nachkommen von x, einschließlich x selbst) eingewurzelt ist. Wir erweisen uns durch die Induktion auf der Höhe von x (die Länge eines längsten einfachen Pfads von x bis ein Nachkomme-Blatt), diese Größe (x)  F, wo d der Grad von x ist.

Grundfall: Wenn x Höhe 0, dann d = 0, und Größe (x) = 1 = F hat.

Induktiver Fall: Nehmen Sie An, dass x positive Höhe und Grad d>0 hat. Lassen Sie y, y..., y die Kinder von x sein, der in der Größenordnung von den Zeiten mit einem Inhaltsverzeichnis versehen ist, die sie am meisten kürzlich Kinder von x (y gemacht das frühste und y das letzte zu sein), und c, c..., c gelassen wurden, ihre jeweiligen Grade zu sein. Wir behaupten dass c  i-2 für jeden ich mit 2id: Kurz bevor y ein Kind von x, y gemacht wurde..., waren y bereits Kinder von x, und so hatte x Grad mindestens i1 damals. Da Bäume nur verbunden werden, wenn die Grade ihrer Wurzeln gleich sind, muss es gewesen sein, dass y auch Grad mindestens i-1 zurzeit hatte, ist es ein Kind von x geworden. Von dieser Zeit zur Gegenwart kann y nur höchstens ein Kind (wie versichert, durch den Markierungsprozess) verloren haben, und so ist sein aktueller Grad c mindestens i2. Das beweist den Anspruch.

Da die Höhen des ganzen y ausschließlich weniger sind als dieser von x, können wir die induktive Hypothese auf sie anwenden, um Größe (y)  F  F = F zu bekommen. Die Knoten x und y, den jeder mindestens 1 beiträgt um (x) nach Größen zu ordnen, und so haben wir

Eine alltägliche Induktion beweist, dass für irgendwelchen der das gewünschte tiefer gibt, zu Größe (x) gebunden hat.

Grenzfall

Obwohl die Gesamtlaufzeit einer Folge von Operationen, die mit einer leeren Struktur anfangen, durch die Grenzen begrenzt wird, die oben, ein (sehr wenige) gegeben sind, können Operationen in der Folge sehr lange nehmen, um zu vollenden (insbesondere löschen und löschen Minimum haben geradlinige Laufzeit im Grenzfall). Aus diesem Grund können Fibonacci Haufen und andere amortisierte Datenstrukturen nicht für Echtzeitsysteme passend sein. Es ist möglich, eine Datenstruktur zu schaffen, die dieselbe Grenzfall-Leistung wie der Haufen von Fibonacci Leistung amortisiert hat. Jedoch ist die resultierende Struktur sehr kompliziert, so ist es in den meisten praktischen Fällen nicht nützlich.

Zusammenfassung von Laufzeiten

(*) Amortisierte Zeit

(**) Mit der trivialen Modifizierung, um einen zusätzlichen Zeigestock zum minimalen Element zu versorgen

(***), Wo n die Größe des größeren Haufens ist

• Brodal, G. S. 1996. Grenzfall effiziente Vorzugswarteschlangen. In Verhandlungen des Siebenten Jährlichen ACM-SIAM Symposiums auf Getrennten Algorithmen (Atlanta, Georgia, die Vereinigten Staaten, am 28-30 Januar 1996). Symposium auf Getrennten Algorithmen. Gesellschaft für die Industrielle und Angewandte Mathematik, Philadelphia, Pennsylvanien, 52-58.

Außenverbindungen

• Java applet Simulation eines Haufens von Fibonacci
• C Durchführung des Haufens von Fibonacci
• MATLAB Durchführung des Haufens von Fibonacci
• De-recursived und Gedächtnis effiziente C Durchführung des Haufens von Fibonacci (free/libre Software, CeCILL-B Lizenz)
• C ++ Schablone Haufen von Fibonacci, mit der Demonstration
• Rubinrote Durchführung des Haufens von Fibonacci (mit Tests)
• Pseudocode des Haufen-Algorithmus von Fibonacci
• Effizienter C ++ Haufen von Fibonacci
• Verschiedene javanische Durchführungen für den Haufen von Fibonacci