Fibonacci-Heaps

Vorbemerkungen:

• Fibonacci-Heaps stellen eine Erweiterung der Binomial-Queues dar und eine weitere Möglichkeit zur Implementierung von Heaps. Die amortisierten Kosten für die Operationen Delete() und DeleteMin() betragen hierbei $\mathcal{O}(\log{n})$, die für alle anderen Heap-Operationen lediglich $\mathcal{O}(1)$. Natürlich können die worst-case-Kosten für ($n\times$ Insert ) + ($n\times$ DeleteMin ) nicht unter $\Omega(n\log{n})$ liegen, denn diese Operationen zusammengenommen stellen einen Sortieralgorithmus dar mit unterer Schranke $\Omega(n\log{n})$.
• Die Verwendung von Fibonacci-Heaps erlaubt eine Verbesserung der Komplexität der Algorithmen für die minimale Spannbäume sowie für Dijkstra's kürzeste-Wege-Algorithmus, denn diese verwenden relativ häufig die DecreaseKey -Operation, welche durch Fibonacci-Heaps billig zu implementieren ist. Bei einem Algorithmus, bei dem die Delete - und

  DeleteMin -Operationen nur einen geringen Anteil der Gesamtoperationen darstellen, sind Fibonacci-Heaps asymptotisch schneller als die Binomial-Queues.

Bemerkungen:

• Priority-Queues eignen sich grundsätzlich nicht für Suchoperationen, unabhängig von ihrer Implementierung. Es ist daher immer eine zusätzliche Datenstruktur, etwa ein Suchbaum, zu verwenden.
• Jedes Element besteht aus einem Schlüssel (key) und einem Wert. Der Schlüssel darf in einer Priority-Queue nur einmal vorkommen. Es ist jedoch zulässig, daß derselbe Datenwert mehreren verschiedenen Schlüsseln zugeordnet ist. Für die folgenden Betrachtungen sind gespeicherte Werte aber uninteressant, es werden nur die Schlüssel betrachtet.