Fibonacci Heap

Zum Beispiel in einem Fibonacci Heap mit den Zahlen 1 bis 10, könnte der Heap wie folgt aussehen:

In diesem Fall ist 1 das minimale Element und steht an der Wurzel des Heaps. Alle Kinder von 1 (also alle anderen Zahlen) sind größer als 1 selbst.

Lass uns ein weiteres konkretes Beispiel ansehen. Angenommen, du fügst aufeinanderfolgend die Zahlen 5, 2, 8 und 1 zum Heap hinzu und entfernst dann das minimale Element. Folgender Python-Code illustriert diese Operationen:

 
    heap = FibonacciHeap()
    heap.insert(5)
    heap.insert(2)
    heap.insert(8)
    heap.insert(1)
    print(heap.remove_min())  # Ausgabe: 1
  

Der Heap passt seine Struktur so an, dass das Minimalelement stets leicht zu finden ist. Nach dem Entfernen des minimalen Elements sieht der Heap wie folgt aus:

Hier ist ein einfacher Code-Auszug in C++, der die grundlegende Struktur und einige Methoden eines Fibonacci Heap demonstriert:

    struct Node {
      int key;
      unsigned int degree;
      bool mark;
      Node *p, *child, *left, *right;
    };
    class FibonacciHeap {
      Node *min;
      unsigned int n;

      public:
        FibonacciHeap() : min(nullptr), n(0) {}
        // Methoden für Heap-Operationen...
    };
  

Beachte, dass in der oben genannten Codeauszug der Data Member 'key' den Wert des Knotens, 'degree' die Ordung des Knotens, 'mark', ob der Knoten markiert ist oder nicht, und 'child', 'left' und 'right sind Zeiger auf die Kindknoten und die Nachbarn des Knotens speichert.

Ein einfacher Java-Code-Auszug, der die Struktur und einige grundlegende Methoden eines Fibonacci Heap demonstriert, könnte folgendermaßen aussehen:

    public class FibonacciHeap {
      private Node min;
      private int size;
      private static class Node {
        int key;
        int degree;
        boolean mark;
        Node parent, child, next, prev;
        // Methoden für die Knotenoperationen...
      }
      // Methoden für Heap-Operationen...
    };
  

In diesem Codeausschnitt sind `min` und `size` die Attribute, die das Minimum und die Größe des Heaps speichern. Die innere `Node`-Klasse speichert den Schlüssel, Grad, Markierungszustand und Zeiger auf die Eltern, Kinder und Nachbarn eines Knoten.

Hier ist ein Python-Codeausschnitt, der die grundlegende Struktur eines Fibonacci Heap zeigt:

    class Node:
      def __init__(self, key):
        self.key = key
        self.degree = 0
        self.mark = False
        self.parent = self.child = self.next = self.prev = None

    class FibonacciHeap:
      def __init__(self):
        self.min = None
        self.size = 0
        # Methoden für Heap-Operationen...
  

Hier definiert die Klasse `Node` einen Knoten im Fibonacci Heap. Jeder Knoten hat Schlüssel-, Grad-, Markierungs-, Eltern-, Kind-, Nachfolger- und Vorgänger-Attribute. Die `FibonacciHeap`-Klasse speichert die Größe des Heaps und einen Zeiger auf das minimale Element.

Die besonderen Eigenschaften des Fibonacci Heap machen ihn für viele Anwendungen attraktiv. Ein Hauptanwendungsfall der Fibonacci Heap Datenstruktur ist in effizienten Algorithmen für Graph-Probleme, wie zum Beispiel Dijkstra's Algorithmus und Prim's Algorithmus. In diesen Algorithmen wird ein Fibonacci Heap genutzt, um die Knoten in einer Warteschlange zu verwalten, dabei ermöglicht die Decrease Key Operation des Fibonacci Heap eine bedeutende Verbesserung in Bezug auf die Leistungsfähigkeit dieser Algorithmen im Vergleich zur Nutzung einfacher Prioritätswarteschlangen.

      // Dijkstra's Algorithmus mit Fibonacci Heap in Pseudocode
      function dijkstra(Graph, source):
          create vertex set Q
          for each vertex v in Graph:
              distance[v] := INFINITY
              previous[v] := UNDEFINED
              add v to Q
          distance[source] := 0 
          while Q is not empty:
              u := vertex in Q with minimum distance
              remove u from Q 
              for each neighbor v of u: // nur v, das noch in Q sind
                  alt := distance[u] + length(u, v)
                  if alt < distance[v]:
                      distance[v] := alt
                      previous[v] := u