Priority Queue

Eine Priority Queue (auch Prioritätswarteschlange genannt) ist eine spezielle Datenstruktur, genauer eine spezielle 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

Von einer Priority Queue wird verlangt, dass sie folgenden Operationen unterstützt:

• INIT (Initialisieren der Priority Queue),
• INSERT (Einfügen eines Elementes in die Priority Queue) und
• EXTRACT_MIN bzw. EXTRACT_MAX (Herausnehmen des Elements mit minimalem bzw. maximalem Schlüssel).

Beispiele

Beispiele für Priority Queues sind

• AVL-Bäume
• Fibonacci-Heaps

Anwendungen

Priority Queues können für die Implementierung diskreter Ereignissimulationen genutzt werden. Dabei werden zu den jeweiligen Ereignissen als Schlüssel die Zeiten berechnet, das Ereignis-Zeit-Paar in die Priority-Queue eingefügt und die Priority Queue gibt dann das jeweils aktuellste (d.h. als nächstes zu verarbeitende) Ereignis aus.