MST: Prim: Datenstrukturen

Die Kostenschätzungen für V $\setminus$ U müssen verwaltet werden. Rechenoperationen sind:

• initialisieren (alles mit + $\infty$)
• Knoten mit geringsten Kosten finden und entfernen
• Kosten ändern (hier: verringern)

Das ist die Schnittstelle für den abstrakten Datentyp Vorrangwarteschlange (priority queue).

Mögliche Implementierungen:

• ungeordnete Liste
• geordnete Liste
• binärer Heap (wie in Heapsort)
• Binomialheap $\to$ Fibonacci-Heap