DeleteMin
: Suche von links den ersten nicht leeren Bucket
j. Falls j=1 ist alles ok (wegen size(1)=1). Falls : Suche minimales Element v im Bucket j (v wird als
FindMin
zurückgegeben und aus der Priority Queue gelöscht), verteile alle
anderen Elemente im Bucket j auf die Buckets , nachdem die u(i)'s, wie folgt, aktualisiert wurden:
u
u
uuu
Kosten für alle
DeleteMins
: pro
DeleteMin
+ .