Autoren: Maciej Krzan, Oliver Krüger

Prioritätswarteschlangen

Prioritätswarteschlange - Definition und Beispiel

Eine Prioritätswarteschlange (auch: Vorrangwarteschlange, Prioritätenliste, Prioritätsschlange) ist eine specielle Art der abstrakte Datenstruktur. Das ist die Erweiterung der Warteschlange. Die Werte bekommen einmalige Schlüssel (jede Schlüssel hat nur ein Wert!) und sie sind in Reihenfolge mit der bestimmte Ordnung. Am meisten der Prioritätswarteschlangen können wir mit Assoziatives Datenfeld oder Heaps realizieren.

Wir können ganz einfach sagen, dass: '''Prioritätswarteschlange ist die abstrakte Datenstruktur, die die Elemente von Menge S deponieren. Diese Elemente haben bestimmte Werte, welche wir können "Schlüssel" heißen und sie sind bis andere Werte in eine Ordnung zusammenpassen.

Beispiel

Person in Pseudocode

Map(String, String) person
 person.insert("Name", "Jens")
 person.insert("Vorname", "Jensen")
 person.insert("Stadt", "Jensfurt")

Assoziatives Datenfeld

Das assoziative Datenfeld (englisch „map“, „dictionary“ oder „associative array“) ist eine Art der abstrakte Datenstruktur. Diese Struktur deponiert die Paare Daten(Schlüssel, Wert), die der Wert und der einmalig Schlüssel haben. Mithilfe bestimmte Schlüssel haben wir der Zutritt bis genau ein Wert.

API den vielen Programmiersprachen nutzen von Assoziatives Datenfeld, z.B.: Java, C++, C#, PHP, Python, Ruby, LISP, D, JavaScript.

Beispiel in C++

Heap

Heap ist die speziell Zufall der Binäre Baum, wo jede "Kind" ist nicht größer als seine "Eltern". Aufgrund diese Bedingungen wir sagen können, dass:

-Würzel muss am größsten sein, oder mit andere am größte Wert haben,

-auf Verknüpfungen(von Würzel bis Blätter) Werte können nicht steigen.

Voll Heap ist, wenn auf alle Niveau (ohne letzte) voll sind und auf letzte Nivou sind den chronologisch Blätter ordnen.

Voll Heap

"Nicht" voll Heap

Prioritätswarteschlangen auf Heap

Auf Heal können wir Prioritätswarteschlangen nutzen und auch bestimmte operationen.

Wir können neue Elemente hinzufügen und bekommen zurück immer am größsten.

Insert

Wir hinzufügen neu Element 17 in erste Plätze in Reihenfolge.

Jetzt müssen wir proben, ob diese neue Element ist größer als seine "Elternteil". Wenn ja, wechseln wir diese Position, wenn nein, bleiben wir wie ist.

Machen wir das so lang (Bild 2), wenn größere Elternteil wir nicht finden, oder im Plätze Würzeln wechseln.