In der Informatik ist eine Vorrangwarteschlange (auch Prioritätenliste, Prioritätsschlange, Prioritätswarteschlange oder genannt) eine spezielle abstrakte Datenstruktur, genauer eine erweiterte Form einer Warteschlange. Den Elementen, die in die Warteschlange gelegt werden, wird ein Schlüssel mitgegeben, der die Reihenfolge der Abarbeitung der Elemente bestimmt.
Operationen Vorrangwarteschlangen müssen die folgenden Operationen unterstützen: insert – Einfügen eines Elements extractMin – Rückgabe und Entfernen des Elements mit dem kleinsten Schlüssel (= höchste Priorität) isEmpty – Überprüfen, ob die Warteschlange leer ist
Daneben gibt es noch Operationen, die vor allem für Online-Algorithmen wichtig sind: remove – Entfernen eines Elements decreaseKey – den Schlüsselwert verringern (d. h. die Priorität erhöhen)
Weitere häufig verwendete Operationen sind: peek – Zurückgeben des Elements mit der höchsten Priorität, ohne die Warteschlange zu verändern merge – Zusammenfügen von zwei Vorrangwarteschlangen
Implementierung Die Implementierung von Vorrangwarteschlangen kann über AVL-Bäume erfolgen. Sowohl insert als auch extractMin können dann in O(log n) Zeit ausgeführt werden. Eine andere Möglichkeit besteht in der Verwendung partiell geordneter Bäume (Heaps). Auch hier liegt die Zeitkomplexität bei O(log n).
Beispiele für Datenstrukturen, die Vorrangwarteschlangen effizient implementieren, sind
AVL-Baum Binärer Heap Binomial-Heap Fibonacci-Heap (amortisierte Laufzeit für remove und extractMin: O(log n), ansonsten O(1), im schlechtesten Fall O(n) bzw. O(log n)) K-Level Buckets Linksbaum Radix-Heap Van-Emde-Boas-Vorrangwarteschlange
Die folgende Tabelle zeigt eine Übersicht über die verschiedenen Laufzeiten von einigen Implementierungen in O-Notation.
Operation peek extractMin insert decreaseKey merge Binärer Heap Θ(1) Θ(log n) O(log n) O(log n) Θ(n) Linksbaum Θ(1) Θ(log n) Θ(log n) O(log n) Θ(log n) Binomial-Heap Θ(1) Θ(log n) Θ(1) Θ(log n) O(log n) Fibonacci-Heap Θ(1) O(log n) Θ(1) Θ(1) Θ(1)
Anwendungen Prioritätswarteschlangen können für die Implementierung diskreter Ereignissimulationen genutzt werden. Dabei werden zu den jeweiligen Ereignissen als Schlüssel die Zeiten berechnet, das Zeit-Ereignis-Paar in die Vorrangwarteschlange eingefügt, und die Vorrangwarteschlange gibt dann das jeweils aktuelle (d. h. als Nächstes zu verarbeitende) Ereignis aus.
Allgemein werden Vorrangwarteschlangen für viele Algorithmen oder sogar Klassen von Algorithmen benötigt.
Zum Beispiel machen Gierige Algorithmen von Prioritätswarteschlangen Gebrauch, da dort häufig das Minimum oder Maximum einer Menge bestimmt werden muss. Einer der bekanntesten Algorithmen dieser Art ist der Algorithmus von Dijkstra zur Berechnung kürzester Wege.
Ebenso kann man Vorrangwarteschlangen für Bestensuche-Algorithmen verwenden. Um in einer Iteration den nächsten vielversprechendsten Knoten zu finden, wird meist eine Vorrangwarteschlange benutzt. Ein Beispiel hierfür ist der A*-Algorithmus, um kürzeste Wege in Graphen zu berechnen.
Ein spezieller Algorithmus, der auch mit Vorrangwarteschlangen implementiert werden kann, ist die Huffman-Kodierung. Die Vorrangwarteschlange wird hierbei dafür verwendet, die Zeichen mit der kleinsten Wahrscheinlichkeit zu finden.
Erweiterungen Neben der klassischen, einendigen Vorrangwarteschlange existieren auch zweiendige. Diese unterstützen zusätzlich eine Operation extractMax, um das Element mit dem größten Schlüssel herauszuziehen. Eine Möglichkeit für die Implementierung solcher Datenstrukturen bieten Doppelheaps. Alternativ können auch Datenstrukturen wie Min-Max-Heaps genutzt werden, die direkt zweiendige Prioritätswarteschlangen unterstützen.
Parallele Vorrangwarteschlange Um Vorrangwarteschlangen weiter zu beschleunigen, kann man sie parallelisieren. Dabei gibt es drei verschiedene Möglichkeiten zur Parallelisierung. Die erste Möglichkeit ist es, einfach die einzelnen Operationen (insert, extractMin …) zu parallelisieren. Die zweite Möglichkeit erlaubt den gleichzeitigen Zugriff von mehreren Prozessen auf die Vorrangwarteschlange. Die letzte Möglichkeit ist es, jede Operation auf k Elementen auszuführen, anstatt immer nur auf einem Element. Im Falle von extractMin beispielsweise würde man die ersten k Elemente mit der höchsten Priorität aus der Vorrangwarteschlange herausnehmen.
Einzelne Operationen parallelisieren Ein einfacher Ansatz um Vorrangwarteschlangen zu parallelisieren ist, die einzelnen Operationen zu parallelisieren. Das heißt, die Warteschlange funktioniert genau so wie eine sequentielle, allerdings werden die einzelnen Operationen durch den Einsatz von mehreren Prozessoren beschleunigt. Der maximale Speedup, der hierbei erreicht werden kann, ist durch beschränkt, da es sequentielle Implementierungen für Vorrangwarteschlangen gibt, deren langsamste Operation in Zeit läuft (z. B. Binomial-Heap).
Auf einem „Concurrent Read, Exclusive Write“-PRAM-Modell (CREW), können die Operationen insert, extractMin, decreaseKey und remove in konstanter Zeit durchgeführt werden, wenn Prozessoren zur Verfügung stehen, wobei die Größe der Vorrangwarteschlange ist. Die Warteschlange ist im Folgenden als Binomial-Heap implementiert. Dabei muss nach jeder Operation gelten, dass maximal drei Bäume derselben Ordnung existieren und dass die kleinste Wurzel der Bäume von Ordnung kleiner als alle Wurzeln von Bäumen höherer Ordnung ist. insert(e): Ein neuer Binomialbaum mit Ordnung 0, dessen einziger Knoten das Element e enthält, wird eingefügt. Danach werden zwei Bäume derselben Ordnung zu einem Baum der Ordnung zusammengefügt, wenn drei Bäume der Ordnung existieren. Der Baum mit der kleinsten Wurzel der Bäume mit Ordnung wird dafür nicht verwendet. Dieser Schritt wird parallel ausgeführt, indem sich jeder Prozessor um die Bäume einer Ordnung kümmert. Somit ist insert in durchführbar. Nachfolgend ist die Operation in Pseudocode aufgeführt.
insert(e) { L = L ∪ e parallelesZusammenfügen()
parallelesZusammenfügen() { für jede Ordnung i parallel: falls |L[i]| >= 3: füge zwei Bäume aus L[i] \ min(L[i]) zu einem neuen Baum b zusammen L[i+1] = L[i+1] ∪ b
extractMin: Das zu entfernende Minimum ist das kleinste Element der Bäume von Ordnung 0. Dieses Element wird entfernt. Um sicherzustellen, dass sich das neue Minimum danach auch in Ordnung 0 befindet, wird für jede Ordnung der Baum mit der kleinsten Wurzel aufgeteilt und die zwei neuen Bäume der Ordnung hinzugefügt. Indem jeder Prozessor genau einer Ordnung zugewiesen wird, kann dieser Schritt parallel in ausgeführt werden. Nach diesem Schritt werden wie bei der insert-Operation zwei Bäume der Ordnung zu einem Baum der Ordnung zusammengefügt, wenn mindestens drei Bäume der Ordnung existieren. Da dieser Schritt auch für jede Ordnung parallel ausgeführt werden kann, ist extractMin in konstanter Zeit ausführbar.
extractMin() { e = min(L) L = L\e für jede Ordnung i parallel: falls |L[i]| >= 1: teile min(L[i]) in zwei Bäume a,b L[i] = L[i] \ min(L[i]) L[i-1] = L[i-1] ∪ {a,b} parallelesZusammenfügen() return e
Das Konzept für konstante Insert- und ExtractMin-Operationen kann erweitert werden, um auch eine konstante Laufzeit für remove zu erreichen. Die DecreaseKey-Operation kann dann durch ein Remove und ein darauffolgendes Insert ebenso in konstanter Zeit realisiert werden.
Der Vorteil dieser Parallelisierung ist, dass sie genau so wie eine normale, sequentielle Vorrangwarteschlange angewendet werden kann. Aber es kann auch nur ein Speedup von erreicht werden. Dieser wird in der Praxis noch weiter dadurch beschränkt, dass bei einer parallelen Implementierung zusätzlicher Aufwand für die Kommunikation zwischen den verschiedenen Prozessoren betrieben werden muss.
Gleichzeitiger paralleler Zugriff Falls der gleichzeitige Zugriff auf eine Vorrangwarteschlange erlaubt ist, können mehrere Prozesse gleichzeitig Operationen auf die Vorrangwarteschlange anwenden. Dies wirft jedoch zwei Probleme auf. Zum einen ist die Semantik der einzelnen Operationen nicht mehr offensichtlich. Zum Beispiel, wenn zwei Prozesse gleichzeitig extractMin ausführen, sollten beide Prozesse das gleiche Element erhalten oder unterschiedliche? Dies schränkt die Parallelität auf die Ebene der Anwendung ein, welche die Vorrangwarteschlange benutzt. Zum anderen gibt es das Problem des Zugriffskonfliktes, da mehrere Prozesse Zugriff auf das gleiche Element haben.mini|Knoten 3 wird hinzugefügt und setzt den Zeiger von Knoten 2 auf Knoten 3. Direkt danach wird Knoten 2 gelöscht und der Zeiger von Knoten 1 auf Knoten 4 gesetzt. Dadurch ist Knoten 3 nicht mehr erreichbar.
Auf einem „Concurrent Read, Concurrent Write“-PRAM-Modell (CRCW) kann der gleichzeitige Zugriff auf eine Vorrangwarteschlange implementiert werden. Im Folgenden ist die Vorrangwarteschlange als Skip-Liste implementiert. Zusätzlich wird eine atomare Synchronisationsprimitive CAS benutzt, um eine Lock-freie Skip-Liste zu ermöglichen. Die Knoten der Skip-Liste bestehen aus einem einzigartigen Schlüssel, einer Priorität, einem Array aus Zeigern auf die nächsten Knoten und aus einem Delete-Kennzeichen. Das Delete-Kennzeichen gibt an, ob der Knoten gerade dabei ist, von einem Prozess gelöscht zu werden. Dadurch wissen die anderen Prozesse, dass der Knoten kurz davor ist gelöscht zu werden und können, je nachdem, welche Operationen sie ausführen, entsprechend darauf reagieren. insert(e): Zuerst wird ein neuer Knoten mit einem Schlüssel und einer Priorität erstellt. Zusätzlich wird dem Knoten noch eine Anzahl an Level übergeben. Dann wird eine Suche gestartet, um die richtige Position in der Skip-Liste zu finden, wo man den neu erstellten Knoten hinzufügen muss. Die Suche startet vom ersten Knoten und vom höchsten Level aus und traversiert die Skip-Liste herunter bis zum niedrigsten Level, bis die korrekte Position gefunden wurde. Dabei wird für jedes Level der zuletzt traversierte Knoten als Vorgängerknoten gespeichert. Zusätzlich wird jener Knoten, zu dem der Zeiger des Vorgängerknoten zeigt, als Nachfolgerknoten gespeichert. Danach wird für jedes Level des neuen Knotens der Zeiger des gespeicherten Vorgängerknotens auf den neuen Knoten gesetzt. Schlussendlich werden noch die Zeiger, für jedes Level, des neuen Knotens auf die entsprechenden Nachfolgerknoten gesetzt. extractMin(): Zuerst wird die Skip-Liste traversiert, bis ein Knoten erreicht wird, dessen Delete-Kennzeichen nicht gesetzt ist. Dann wird das Delete-Kennzeichen für diesen Knoten gesetzt. Abschließend werden die Zeiger des Vorgängerknotens aktualisiert. Beim Erlauben vom gleichzeitigen Zugriff auf eine Vorrangwarteschlange muss darauf geachtet werden, dass es zu möglichen Konflikten zwischen zwei Prozessen kommen kann. Zum Beispiel kann es zu einem Konflikt kommen, falls ein Prozess versucht, einen Knoten hinzuzufügen, aber ein anderer Prozess schon dabei ist, seinen Vorgängerknoten zu löschen. Die Gefahr besteht, dass der neue Knoten zwar zur Skip-Liste hinzugefügt wurde, aber nun nicht mehr erreichbar ist. (Siehe Bild)
K-Element-Operationen Bei dieser Art der Parallelisierung von Vorrangwarteschlangen werden neue Operationen eingeführt, die nicht mehr ein einzelnes Element bearbeiten, sondern Elemente gleichzeitig. Die neue Operation k_extractMin löscht dann die kleinsten Elemente aus der Vorrangwarteschlange und gibt sie zurück. Dabei ist die Warteschlange auf verteiltem Speicher parallelisiert. Jeder Prozessor hat seinen eigenen privaten Speicher und eine lokale (sequentielle) Vorrangwarteschlange. Die Elemente der globalen Warteschlange sind also auf alle Prozessoren verteilt.