Datenstrukturen: Priority Queue / Warteschlange mit Priorität

Die Warteschlange mit Priorität

Neben der Queue gibt es noch eine erweiterte Variante, genannt Priority Queue (deutsch: Prioritäts-Warteschlange).
Im Vergleich zu einer normalen Queue wird jedem Objekt ein Prioritätswert mitübergeben. Dieser hat einen Wertebereich von 0 ... n.
Dieser Prioritätswert sorgt dafür, dass sich Objekte "vordrängeln" dürfen. Sie werden also schneller verarbeitet, da Sie bevorzugt zu dem Listenanfang durchgereicht werden. Im Gegensatz zu Listen, Stacks und Queues spielt hier die Einfügereihenfolge keine Rolle.

Soll ein Objekt in die Priority Queue (nachfolgend PQ) eingefügt werden, so wird die PQ zunächst bis zu dem Wert durchlaufen. Anschließend wird das Objekt dort eingefügt, wo der Prioritätswert (nachfolgend PW) gleich oder höher ist. Das heißt, die Nachfolgenden Objekte werden um einen Index weiter nach hinten zum Listenende verschoben.

Weiterhin ist es mit einer PQ möglich, den PW eines Objektes zu verändern. Dadurch kommt es Gegebenenfalls zu Neuanordnungen der Objekte. Man sollte möglichst versuchen direkt zu Beginn einen geeigneten PW zu wählen, da das neue Anordnen von Objekten dauern kann. Je nach Listengröße.
Wird ein Objekt aus der PQ entnommen, so ist es das Objekt mit dem höchsten PW, welches sich am Listenanfang befindet.

Abbildung: Eine Prioritätswarteschlange

Anwendungsbeispiel

• Die Prioritätswarteschlange wird bei der Prozessverwaltung eingesetzt (Round Robin). Jeder Prozess bekommt eine Zeitscheibe lang Zeit. Ist die Zeit abgelaufen, so reiht sich dieser Prozess wieder weiter hinten in die PQ ein. Der PW wird entsprechend erhöht. Es sei denn der Prozess ist beendet.
  Eine normale Queue wäre hier keine gute Wahl, da es zum sogenannten starvation (verhungern) kommen kann. Das bedeutet, ein Prozess welcher lange dauert kommt nie zur Ausführung.

• Auf Ein- und Ausgabegeräte (I/O-Devices) soll schneller reagiert werden, als auf die Aktualisierung einzelner GUI-Elemente

• Eine Anwendung zur Verwaltung von Terminen

Quelle
https://www.cs.princeton.edu/~rs/AlgsDS07/06PriorityQueues.pdf, p. 3ff.
www.callicoder.com/assets/images/post/large/priority-queue-data-structure.jpg