Datenstrukturen: Priority Queue / Warteschlange mit Priorität

11개월 전

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.

pq.jpg
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

Authors get paid when people like you upvote their post.
If you enjoyed what you read here, create your account today and start earning FREE STEEM!
STEEMKR.COM IS SPONSORED BY
ADVERTISEMENT
Sort Order:  trending

Steem on und weiter viel Erfolg...

Du hast ein kleines Upvote vom German-Steem-Bootcamp erhalten.

Du findest uns im Discord unter https://discord.gg/HVh2X9B

Aktueller Kurator ist @don-thomas

N E U SAMSTAGS findet jetzt bei uns ab 22 Uhr die Quasselstunde(n) statt wo du nicht nur mit uns reden kannst - es werden auch tolle Preise verlost
Du möchtest keine Upvotes (mehr) von uns erhalten? Eine kurze Mittelung unter diesen Kommentar reicht.
Dem Upvote von uns folgt ein Trail der weitere Upvotes von unseren Unterstützern beinhaltet. Hier kannst du sehen wer diese sind und auch erfahren wie auch du uns und somit die deutschsprachige Community unterstützen kannst.
·

Dankeschön