Wir wählen einen ungeordneten (a, 2a)-Baum, der wie folgt aufgebaut ist:

1. Die Blätter enthalten die Elemente (Dist(u), u) in beliebiger Reihenfolge
2. Jeder innere Knoten v enthält den minimalen Wert eines Blattes unter v mit Zeiger auf dieses Blatt.
3. Ein zusätzliches Zeigerfeld Pointer[1,...,n], wobei Pointer(u) auf das Blatt zeigt, das u enthält, bzw. Pointer(u) = nil, falls u nicht in U liegt.

Ein ungeordneter (a, 2a)-Baum mit n Blättern hat eine Höhe von O(log n / log a).
Damit ergeben sich folgende Laufzeiten für die einzelnen Operationen:

• Finde Minimum: in O(1).
• Lösche Minimum: entferne das Blatt (das durch den Minimumanzeiger gegeben ist), gehe aufwärts zur Wurzel und repariere den (a, 2a) Baum durch Verschmelzen und Stehlen mit konstant vielen Operationen pro Knoten. Das Minimum unter einem Knoten v wird durch das Minimum aus den Söhnen gebildet, d.h. es kann in O(2a) = O(a) Schritten neu berechnet werden. Damit ergibt sich eine Laufzeit von
  
  O(a log n / log a)
  
  

• Einfügen: analog zum Löschen werden Knoten gespalten und das Minimum jeweils neu berechnet. Auch dafür beträgt die Laufzeit
  
  O(a log n / log a)
  
  

• Verringere Inhalt eines Blattes mit Zeiger. Wir verändern den Wert des Blattes und gehen rückwärts zur Wurzel. Hat ein Knoten einen Minimalwert der größer ist als der geänderte Wert, so biege das Minimum um.

Nach Lemma 3 ergibt sich eine Laufzeit von O(n a log n / log a + m log n / log a).

Beweis: (i) wähle a=n. (ii) wähle a=2.

---