Fibonacci-Heap
Ein Fibonacci-Heap ist eine Datenstruktur zur Implementation einer
Priority Queue, die erstmals 1987 von Fredman und Tarjan 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 eines leichtesten Elements ist amortisiert in
möglich.
Der Algorithmus von Dijkstra zum Finden aller kürzesten Pfade beziehungswiese der Algorithmus von Prim zum Finden eines minimal spannenden Baumes in einem Graphen lassen sich mit Fibonacci-Heaps mit einer Laufzeit von implementieren.
Websites:
Tagoror |
Guajara |
Tacoronte Guia |
Todo Gomera |
Deranet |
Radioaficionados |
Cinebso |
Mi Buscador
Enciclopedia On Line:
GNU FDL.
