Vorrangwarteschlange

Grundidee und grundlegende Operationen

Eine Vorrangwarteschlange ist eine abstrakte Datenstruktur und eine erweiterte Form der Warteschlange. Jedes eingefügte Element erhält einen Schlüssel. Dieser bestimmt, in welcher Reihenfolge die Elemente abgearbeitet werden. Dabei gilt: Das Element mit dem kleinsten Schlüssel besitzt die höchste Priorität.

Die drei grundlegenden Operationen sind:

• insert: Fügt ein Element ein.
• extractMin: Gibt das Element mit dem kleinsten Schlüssel zurück und entfernt es.
• isEmpty: Prüft, ob die Warteschlange leer ist.

Besonders für Online-Algorithmen, die Eingaben schrittweise verarbeiten, sind außerdem remove zum Entfernen eines bestimmten Elements und decreaseKey zum Verringern seines Schlüssels wichtig. decreaseKey erhöht damit die Priorität des Elements. Häufig gibt es auch peek, das das Element mit der höchsten Priorität zurückgibt, ohne die Warteschlange zu verändern, sowie merge zum Zusammenfügen zweier Vorrangwarteschlangen.

Implementierungen und Laufzeiten

Vorrangwarteschlangen lassen sich unter anderem mit AVL-Bäumen oder partiell geordneten Bäumen, sogenannten Heaps, implementieren. Bei beiden Ansätzen können insert und extractMin in O(log n) Zeit ausgeführt werden, wobei n die Zahl der gespeicherten Elemente bezeichnet.

Geeignete Datenstrukturen sind AVL-Bäume, binäre Heaps, Binomial-Heaps, Fibonacci-Heaps, K-Level Buckets, Linksbäume, Radix-Heaps und Van-Emde-Boas-Vorrangwarteschlangen. Ihre Stärken unterscheiden sich je nach Operation:

• Binärer Heap: peek benötigt Θ(1), extractMin Θ(log n), insert und decreaseKey jeweils O(log n), merge Θ(n).
• Linksbaum: peek benötigt Θ(1), extractMin und insert jeweils Θ(log n), decreaseKey O(log n), merge Θ(log n).
• Binomial-Heap: peek und insert benötigen jeweils Θ(1), extractMin und decreaseKey jeweils Θ(log n), merge O(log n).
• Fibonacci-Heap: peek, insert, decreaseKey und merge benötigen jeweils Θ(1), extractMin O(log n).

Beim Fibonacci-Heap gelten für remove und extractMin amortisierte Laufzeiten von O(log n), für die übrigen Operationen O(1). „Amortisiert“ bedeutet, dass die durchschnittlichen Kosten über eine Folge von Operationen betrachtet werden. Im schlechtesten Fall liegen die Laufzeiten laut Artikel bei O(n) beziehungsweise O(log n).

Anwendungen und zweiendige Variante

Vorrangwarteschlangen werden in vielen Algorithmen eingesetzt, wenn wiederholt das kleinste oder größte Element einer Menge ausgewählt werden muss.

Bei diskreten Ereignissimulationen wird zu jedem Ereignis seine Ausführungszeit als Schlüssel berechnet. Das Zeit-Ereignis-Paar wird eingefügt; anschließend liefert die Vorrangwarteschlange jeweils das als Nächstes zu verarbeitende Ereignis.

Gierige Algorithmen nutzen Vorrangwarteschlangen häufig zur Auswahl eines Minimums oder Maximums. Ein bekanntes Beispiel ist der Algorithmus von Dijkstra zur Berechnung kürzester Wege. Auch Bestensuche-Algorithmen wählen damit in jeder Iteration den vielversprechendsten Knoten aus. Dazu gehört der A*-Algorithmus für kürzeste Wege in Graphen. Bei der Huffman-Kodierung dient die Datenstruktur dazu, Zeichen mit der kleinsten Wahrscheinlichkeit zu finden.

Die klassische Vorrangwarteschlange ist einendig und entnimmt nur das Element mit dem kleinsten Schlüssel. Eine zweiendige Vorrangwarteschlange unterstützt zusätzlich extractMax, also das Entnehmen des Elements mit dem größten Schlüssel. Sie kann beispielsweise mit Doppelheaps oder mit Min-Max-Heaps umgesetzt werden.

Formen der Parallelisierung

Parallele Vorrangwarteschlangen sollen die Verarbeitung beschleunigen. Der Artikel unterscheidet drei Ansätze:

• Einzelne Operationen wie insert oder extractMin werden intern auf mehrere Prozessoren verteilt.
• Mehrere Prozesse dürfen gleichzeitig auf dieselbe Vorrangwarteschlange zugreifen.
• Eine Operation verarbeitet k Elemente gleichzeitig, beispielsweise entfernt k_extractMin die k Elemente mit der höchsten Priorität.

Die Ansätze haben unterschiedliche Ziele und Grenzen. Das Parallelisieren einzelner Operationen behält das Verhalten einer gewöhnlichen Vorrangwarteschlange bei. Gleichzeitiger Zugriff steigert die Parallelität auf Anwendungsebene, benötigt aber eine klare Semantik und Schutz vor Zugriffskonflikten. K-Element-Operationen können einen größeren Durchsatz erzielen, sind jedoch nicht mit jedem Algorithmus vereinbar.

Parallelisierte Einzeloperationen und gleichzeitiger Zugriff

Werden nur die einzelnen Operationen parallelisiert, verhält sich die Datenstruktur nach außen wie eine sequentielle Vorrangwarteschlange. Der maximale Speedup ist auf O(log(n)) beschränkt, weil sequentielle Implementierungen wie der Binomial-Heap bereits ihre langsamste Operation in O(log(n)) Zeit ausführen. Kommunikationsaufwand zwischen den Prozessoren begrenzt die praktische Beschleunigung zusätzlich.

Auf einem CREW-PRAM-Modell („Concurrent Read, Exclusive Write“) können insert, extractMin, decreaseKey und remove mit O(log(n)) Prozessoren in konstanter Zeit ausgeführt werden. Die beschriebene Implementierung verwendet einen Binomial-Heap. Nach jeder Operation dürfen höchstens drei Bäume derselben Ordnung vorhanden sein; außerdem muss die kleinste Wurzel der Bäume der Ordnung i kleiner sein als alle Wurzeln von Bäumen höherer Ordnung.

Bei insert entsteht zunächst ein Binomialbaum der Ordnung 0. Existieren drei Bäume der Ordnung i, werden zwei davon zu einem Baum der Ordnung i+1 verbunden; der Baum mit der kleinsten Wurzel bleibt unberührt. Je ein Prozessor bearbeitet eine Ordnung, sodass dies parallel in O(1) möglich ist.

Bei extractMin wird das kleinste Element der Bäume der Ordnung 0 entfernt. Für jede höhere Ordnung wird der Baum mit der kleinsten Wurzel aufgeteilt, sodass zwei Bäume der nächstniedrigeren Ordnung entstehen. Danach werden überzählige Bäume wie bei insert zusammengefügt. Auch dies ist mit je einem Prozessor pro Ordnung in O(1) möglich. Das Verfahren lässt sich auf remove erweitern; decreaseKey kann als remove mit anschließendem insert realisiert werden.

Beim gleichzeitigen Zugriff mehrerer Prozesse sind dagegen Semantik und Zugriffskonflikte problematisch. So muss festgelegt werden, ob zwei gleichzeitige extractMin-Aufrufe dasselbe oder verschiedene Elemente erhalten. Zudem kann ein neu eingefügter Knoten unerreichbar werden, wenn gleichzeitig sein Vorgängerknoten gelöscht und dessen Zeiger verändert wird.

Auf einem CRCW-PRAM-Modell („Concurrent Read, Concurrent Write“) kann eine Lock-freie Skip-Liste verwendet werden. Die atomare Synchronisationsoperation CAS koordiniert konkurrierende Änderungen. Jeder Knoten besitzt einen einzigartigen Schlüssel, eine Priorität, ein Array von Zeigern auf nachfolgende Knoten und ein Delete-Kennzeichen. Dieses zeigt anderen Prozessen an, dass der Knoten gerade gelöscht wird.

Beim Einfügen wird die richtige Position vom höchsten bis zum niedrigsten Level gesucht. Vorgänger und Nachfolger werden für jedes Level gespeichert und die Zeiger entsprechend angepasst. extractMin traversiert die Liste bis zum ersten Knoten ohne Delete-Kennzeichen, setzt dieses Kennzeichen und aktualisiert anschließend die Zeiger des Vorgängers. Konflikte müssen besonders berücksichtigt werden, wenn ein Prozess einfügt, während ein anderer den zugehörigen Vorgänger löscht.

Operationen auf k Elementen

Bei K-Element-Operationen verarbeitet eine Operation mehrere Elemente zugleich. k_extractMin entfernt und liefert die k kleinsten Elemente. Die globale Vorrangwarteschlange liegt dabei auf verteiltem Speicher: Jeder Prozessor besitzt einen privaten Speicher und eine lokale, sequentielle Vorrangwarteschlange.

Bei k_insert werden die einzufügenden Elemente zufällig und gleichverteilt den Prozessoren zugewiesen. Einzelne Elemente können weiterhin eingefügt werden. Mit hoher Wahrscheinlichkeit befinden sich die global kleinsten Elemente dadurch in der Vereinigung der lokal kleinsten Elemente aller Prozessoren.

Für k_extractMin werden aus jeder lokalen Warteschlange zunächst die m kleinsten Elemente entfernt und in einer Ergebnismenge gesammelt. Die Elemente bleiben ihrem ursprünglichen Prozessor zugeordnet. m hängt von k und der Prozessorzahl p ab. Durch parallele Selektion werden die k kleinsten Elemente der Ergebnismenge bestimmt. Sind sie noch nicht die global k kleinsten, werden erneut jeweils m lokale Elemente entnommen. Sobald die Ergebnismenge alle gesuchten Elemente enthält, werden diese zurückgegeben; die übrigen Elemente kommen zurück in ihre ursprünglichen lokalen Warteschlangen. Eine Verbesserung besteht darin, die Ergebnismenge nicht nach jeder Operation sofort vollständig wieder einzufügen, um unnötiges Entfernen und erneutes Einfügen zu vermeiden.

Die erwartete Laufzeit von k_extractMin beträgt O((k/p) log(n)), sofern k = Ω(p · log(p)) gilt und n die Größe der Vorrangwarteschlange ist. Das gleichzeitige Entfernen mehrerer Elemente kann gegenüber einer sequentiellen Warteschlange deutlich schneller sein.

Nicht jeder Algorithmus kann diesen Ansatz verwenden. Beim Dijkstra-Algorithmus wird jeweils der Knoten mit der kleinsten Distanz entnommen; anschließend werden seine Kanten relaxiert, wodurch sich die Prioritäten benachbarter Knoten ändern können. Würden k Knoten gleichzeitig entnommen, könnte die Bearbeitung eines Knotens die Priorität eines anderen bereits entnommenen Knotens verändern. Dieser würde möglicherweise zu früh als besucht markiert, obwohl seine gefundene Distanz noch nicht minimal ist. K-Element-Operationen zerstören hier die Label-Setting-Eigenschaft des Dijkstra-Algorithmus.