Diskussion:Fibonacci-Heap
koennte jemand genauer erlaeutern, wozu DECREASE_KEY benoetigt wird? danke! Pinguin.tk 08:40, 1. Sep 2004 (CEST)
Für Dijkstras Algorithmus zur Bestimmung von kürzesten Wegen in einem Graphen benötigt man eine möglichst effiziente Vorrangwarteschlange. Ein Fibonacci-Heap ist eine mögliche Realisierung davon.
In diesem Anwendungsfall ist jedes Element der Schlange ein möglichst kurzer Weg zu einem bestimmten Knoten in einem Graphen. Während der Suche wird jeder besuchte Knoten mit dem besten bis dahin bekannten Weg in die Schlange eingetragen. Findet man später einen kürzeren Weg zu demselben Knoten, so aktualisiert man das Element in der Schlange mit der Operation decreaseKey. Das ist u.U. wesentlich effizienter als die Kombination von remove(alt) und insert(neu).
--HWellmann 21:14, 1. Feb 2005 (CET)
Fehler bei den Laufzeiten
Es ist nicht richtig, dass alle Operationen (außer remove und extractMin) in O(log n) tatsächlicher Zeit ausgeführt werden können. Auch decreasekey kann im worst case linear viele Schritte benötigen: die Tiefe eines Fibonacci-Baums ist nämlich nicht logarithmisch beschränkt. Daher kann es sein, dass ein "unärer" Baum entsteht, also zu einer "senkrechten" linearen Liste degeneriert, bei der alle Knoten (außer der Wurzel) markiert sind und folglich bei einer decreasekey-Operation kaskadierend abgetrennt werden müssen. Entsprechende Beispiele lassen sich für alle n konstruieren.
Den Fehler findet man des Öfteren (allerdings nicht im englischsprachigen Wikipedia-Artikel) -- er wird im Buch Introduction to Algorithms von Cormen et al. in einer Übungsaufgabe zu den F-Heaps auch thematisiert.
Ich würde den Abschnitt gern entsprechend ändern, werde damit aber noch warten, ob jemand anderer Meinung ist.
-- MrHomn, 16. Mai 2006
- Bin noch am drüber Nachdenken bzw. Infos suchen :-) Auf den ersten Blick scheint mir das auch möglich zu sein, aber warum steht es dann praktisch überall sonst falsch? --thth 11:34, 28. Mai 2006 (CEST)
- Sorry, habe nichts dazu rausgefunden (na hoffentlich kommt das nicht in meiner Prüfung dran ... :-) Evtl. würde es helfen auf online verfügbare Infos dazu zu verweisen, damit man sich selber mal ein Bild machen kann. Wenn es aber wirklich sein kann und entsprechende Infos vorliegen sehe ich eigentlich keinen Grund, das nicht zu korrigieren. --thth 11:49, 18. Jun 2006 (CEST)
- [1] sollte helfen.
- -- Bastian, 06.03.02
Nochwas zu den Laufzeiten - es gibt dort eine Passage "...amortisiert sind die Kosten für fast alle anderen Operationen allerdings konstant, das heißt O(1).". Ich störe mich etwas am "fast alle anderen Operationen" - da könnte also auch eine mit exponentieller Laufzeit dabei sein =) Generell - wie wäre es mit einer kleinen Tabelle "Operation - Laufzeit (wc) - Amortisierte Laufzeit" ? --OOo.Rax 16:17, 15. Sep. 2007 (CEST)
Fehler bei Anwendungen
da steht was von wegen implementierung von dijkstra und prim mit fibonacci heaps in nlogn + m, während implementierung mit avl-baum dauert nlogn + mlogn. ne implementierung von dijkstra mit avl-baum würde ich gerne mal sehen, denke aber das müsste binomial queue heissen..
-- ak, 14.9.06
- seh ich auch so :-) --Koethnig 03:28, 15. Sep 2006 (CEST)
Fehlerhafter Bezug zu Fibonacci-Bäume
"Ein Fibonacci-Heap besteht aus einer Liste von Fibonacci-Bäumen". Das ist total falsch! Derjenige, der das geschrieben hat, hat sich ggf. nicht angeschaut, was ein Fibonacci-Baum ist! Ein Fibonacci-Heap hat seinen Namen nicht wegen der Fibonacci-Bäum (auch wenn das nahe läge, da der Binomial-Heap seinen namen ja von den Binomial-Bäumen hat), sondern von den Fibonacci-Zahlen, die bei der Laufzeitanalyse vorkommen... Bitte korrigiert das mal jemand, der sich auskennt.
Es macht auch keinen Sinn, um es mal logisch anzugehen, denn wenn man ohne Reorganisierung Knoten einfügt und löscht kann schon allein die AVL-Bedingung (denen Fibonacci-Bäumen unterworfen sind) nicht eingehalten werden, geschweige denn die Fibonacci-Baum-Bedingung selbst.
Wer mir nicht glaubt, kann ja auch das hier lesen: http://portal.acm.org/citation.cfm?doid=28869.28874 Das ist das Originalpaper, wo die Dinger zuerst vorgestellt wurden.
Was für eine lineare Liste
Das muss auf jeden Fall notiert werden, sie könnte ja z.B. auch sortiert sein. Ich weiß nicht, was der Autor sich gedacht hat, aber ich denke mal, sie soll unsortiert sein, wobei der Beste immer Zwischengespeichert wird. --Chricho 23:19, 13. Jul. 2010 (CEST)
Es gibt mehr als einen Listentyp
Was mich sehr verwirrt ist die Vergleichsangabe mit den Listen und sortierten Listen. Listen sind für eine komplette Unterdisziplin der Datenstrukturen und es gibt mehr als eine Art von Listen hier nur mal die wichtigsten aufgelistet:
* SkipList * ArrayList * LinkedList * TreeList
Sortierte TreeLists haben bis auf die "Create Heap" Eigenschaft die exakt die gleichen Komplexitäten wie ein Min-Heap. SkipLists haben probabilistisch gesehen diesselben Eigenschaften wie eine TreeList. Sortierte ArrayLists haben ein amortisiertes "Remove Min" von O(1), wenn man sie clever implementiert. Die sortierte LinkedList hat ein garantiertes "Remove Min" von O(1). (nicht signierter Beitrag von 92.192.44.93 (Diskussion) 09:49, 23. Apr. 2013 (CEST))
- Wenn einfach nur von Listen geredet wird, dann ist i.d.R. die Rede von den allereinfachsten Listen, wie man sie bei Liste (Datenstruktur) findet: die einfach verketteten. Soll die Liste weitere Eigenschaften haben (sortiert, doppelt verkettet, oder gar eine der oben genannten Varianten), dann muß das extra ausgesprochen werden. So kenne ich die Literatur, und hier in WP machen wir es auch so, denke ich. --H.Marxen (Diskussion) 22:33, 23. Apr. 2013 (CEST)
Die Amerikaner haben uns wie so oft wohl begrifflich etwas vorraus, was die Klarheit anbelangt: http://en.wikipedia.org/wiki/List_%28abstract_data_type%29 (nicht signierter Beitrag von 92.192.100.133 (Diskussion) 19:04, 24. Apr. 2013 (CEST))
