Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenDonnerstag, 19. September 2019 

Fibonacci-Heap


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Ein Fibonacci-Heap ist eine Datenstruktur zur Implementation einer Priority Queue die erstmals 1987 von Fredman und beschrieben wurde. Im Gegensatz zu einem Binären Heap können in einem Fibonacci-Heap die Operationen Insert (einfügen eines neuen Elementes) und Decrease Key (Ändern des Gewichtes eines Elementes) in amortisiert konstanter Zeit ausgeführt werden. Das Entfernen leichtesten Elements ist amortisiert in <math>O(\log{n})</math> möglich.

Der Algorithmus von Dijkstra zum Finden aller kürzesten Pfade beziehungswiese Algorithmus von Prim zum Finden eines minimal spannenden Baumes in einem Graphen lassen sich mit Fibonacci-Heaps mit einer von <math>O(n\log{n} + m)</math> implementieren.



Bücher zum Thema Fibonacci-Heap

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Fibonacci-Heap.html">Fibonacci-Heap </a>