cards-deck: 100-199_university::111-120_theoretic_cs::111_algorithms_datastructures

Priority Queues | Queues more specific:

anchored to [[111.00_anchor]]

Previously we’ve introduced the datastructure concept of a [[111.08_algo_datastructures#Queues Warteschlangen|Queue]]

Motivation:

Consider an emergency department in a hospital. Usually there’s a constant flow of new patients being added that have to be treated. Now there might be patients with far worse conditions that require immediate treatment, while others are not that bound or don’t require immediate actions. SO we assign each patient a priority after which we decide when to treat them.

This is the whole intuition of a priority queue:

we have normal patients that are just fed to the queue and served one after the other
we have special priorities that will influence the order of patients being treated

Theres another example: Consider a computer cluster that requires to compute jobs constantly. Usually jobs come in all the time and are assigned a space in the queue ( without any priorities etc!) However sometimes there are jobs that have a higher priority and thus need to jump over the queue to be executed next / first.

Anforderungen | Priority Queue:

Betrachten wir das Konzept einer Priority Queue möchten wir bestimmte Eigenschaften erfüllen, um entsprechend von einer sprechen zu können. Folgende wollen wir also umsetzen welche Anforderungen haben wir? #card

eine Datenstruktur, die eine Menge $S$ entsprechend verwalten und ihre Struktur einhalten kann.
jedes Element dieser weist einen Wert zur Beschreibung deren Priorität auf
insofern wir ein Element aus der Queue entfernen –> möchten wir das nächste mit höchster Priorität schnell erhalten können ( also etwa den Heap passend aktualisieren.) ^1704708740864

Implementationen der Daten-Struktur:

Wir wollen diese Datenstruktur relativ schnell aufbauen, sodass Operationen des Entfernen, Einfügen und Verändern in möglichst geringer Zeit ablaufen können. Folgende Ansätz versuchen diese Struktur sinnig zu implementieren.

Naiv | unsorted Arrays | Lists:

Wir können naiv versuchen einen unsortierten Array oder Liste aufzubauen. Betrachten wir diese einfache Implementation was sind dessen Vorteile? #card Das einfügen: ist relativ einfach, weil wir das neue Element ans Ende setzen können. Somit $O (1)$ Entfernen bzw. finden: Also das finden und anschließend entfernen, des Items mit der höchsten Priorität -< ist leider sehr teuer mit $O (n)$

wir müssen den ganzen Array durchsuchen, und so eventuell die ganze Liste. Vergrößern/ Verkleiner einer Priorität: ist relativ einfach wenn wir wissen, wo sich etwas befindet. Wissen wir das, dann folgt $O (1)$ ^1704708740876

Soweit klingt es gut, aber wir haben das Problem, dass die Suche nach dem größten Element bzw dessen mit der höchsten Priorität nicht gerade gut ist und mit $n$ skalieren wird.

Naiv | sorted Arrays | Lists:

Unsortierte Arrays | Listen brauchten lang, um ein Element mit hoher Priorität zu finden. Das wollen wir nun mit einem sortierten Array verhindern, da bei diesem die Liste bereits vorsortiert ist. Wie verhält es sich dann mit der Suche, einfügen und Löschen? #card Zuerst muss die Liste bzw der Array sortiert werden. Dadurch haben wir schon einen Aufwand von Kosten –> $O (n lo g n)$ Weiterhin werden jett die typischen Operationen ausgeführt und werden so auch eine Zeit in Anspruch nehmen! Entfernen bzw finden: ist relativ einfach, weil wir immer wissen, wo das größte Element ist –> also das mit der höchsten Priorität Das Einfügen gestaltet sich jetzt jedoch schwieriger, denn wir müssen erst suchen und dann finden. -> beim Array haben wir die Schwierigkeit, dass zuerst mit binary search der Eintrag gefunden werden muss $O (n lo g n)$ und anschließend noch alle Einträge nach rechts verschoben werden müssen, also $O (n)$ –> dadurch sind wir langsam -> bei der Liste können wir keine binary search anwenden, und müssen so jedes Element traversieren, bis wir das neue Element einfügen können. Daraus folgt im schlimmsten Fall $O (n)$ ( also nichts ist besser geworden) Vergrößern / Verkleinern einer Priorität: Auch das ist schwierig bzw teuer, denn wir müssen den Eintrag anschließend neu einordnen, was uns ( wie bekannt) im schlimmsten Fall $O (n)$ kosten wird! ^1704708740885

Die vorherigen Implementationen schienen jetzt nicht entsprechend und man kann diese noch besser bzw effizienter gestalten und umsetzen. Dafür möchten wir nochmals die [[111.09_heaps]] betrachten:

Clever | Heaps, but modified:

Zuvor betrachtete Datenstrukturen haben in ihrer Ausführung für diverse grundlegende Operationen langsame Faktoren, weswegen wir sie damit vielleicht nicht umsetzen möchten bzw. sollten.

Ferner betrachten wir jetzt die Bildung der priority Queue durch einen Heap: was müssen wir beachten, wie können wir das umsetzen? #card

wir müssen auch hier vorzeitig erstmal den Heap aufbauen, also die Menge von Inhalten entsprechend der Vorbedingungen etablieren.
Etwas hinzufügen, können wir jetzt durch InsertElement -> der Funktion, die ein neues Element einfügt und anschließend den Heap sortieren wird.
das Maxima entfernen/finden, können wir auch relativ einfach umsetzen. Dafür nehmen wir das Item der Wurzel und tauschen anschließend ein Item aus den tiefsten Zweigen in den neuen Platz. Danach sortiert sich der Heap wieder.
Vergrößern / Verkleinern einer Priorität: Auch hier werden wir den angewählten Inhalt aktualisieren und anschließend den heap sich neu sortieren lassen. ^1704708740893

Die resultierenden Laufzeiten: welche können wir für einfügen, entfernen, verändern betrachtne? #card Die Prämisse: Der Heap muss gebaut werden, also $O (n)$

Einfügen $O (lo g n)$
Entfernen $O (lo g n)$
Anpassen: $O (lo g n)$ ^1704708740902

Hier sehen wir die Vorteile von Heaps:

sie sind in ihrere Handbarkeit zwischen sortierten und unsortierten Arrays angestzt und somit nicht ganz so schnell aber manchmal schneller als die Alternative Möglichkeit. Also $O (1) < O (lo g n) < O (n)$

scattered-lenity