Vorrangwarteschlange
In der Informatik ist eine Vorrangwarteschlange (auch Prioritätenliste, Prioritätsschlange, Prioritätswarteschlange oder englisch priority queue 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 Operationen
- insert, zum Einfügen eines Elementes und
- extractMin, zur Rückgabe und zum Entfernen des Elements mit dem kleinsten Schlüssel (= höchster Priorität)
unterstützen.
Daneben gibt es noch Operationen, die vor allem für Online-Algorithmen wichtig sind:
- remove entfernen eines Elements
- decreaseKey den Schlüsselwert verringern (=die Priorität erhöhen)
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), Worst Case O(n) bzw. O(log n))
- K-Level Buckets
- Linksbaum
- Radix Heap
- Van-Emde-Boas-Vorrangwarteschlange
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.
Gierige Algorithmen machen ebenfalls 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.
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.
Literatur
- George F. Luger: Künstliche Intelligenz. Strategien zur Lösung komplexer Probleme. 2001, ISBN 3-8273-7002-7
Weblinks
java.util.PriorityQueuein der Java API bei Oracle (englisch)