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.

Impressum • Lesezeichen setzen • Seite versenden • Seite drucken

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