AuK/Prioritätswarteschlangen WS13-14

Wiki-Quelltext dieser Seite.

<language>Processing</language>
'''Autoren:''' [mailto:s3makrza@stud.hszg.de Maciej Krzan], [mailto:s3olkrue@stud.hszg.de Oliver Krüger]














=Warteschlange=

Benutzen das "First in, First out" Prinzip. Es kann eine beliebige Menge von Objekten aufnehmen und gibt diese in der Reihenfolge ihres Einfügens wieder zurück

Beispiele für Warteschlangen sind Autos an einer Zapfsäule, Warteschlange im Supermarkt, Patienten im Wartezimmer, Prozesse in einem Computerbetriebssystem.


= 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.
:

===Operationen===

insert() - zum einfügen von element x in die menge S

Delete() - entfernt element x aus der menge S

ExtractMin() - entfernt element x mit dem kleinsten Schlüssel

FindMin() - element x mit dem kleinsten Schlüssel wird zurückgegeben

DecreaseKey() - verringert den Schlüsselwert von element x

===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++===
<code id="52ac572aa5f0c">
#include <map>
using namespace std;
map<string, int> anzahl_tage; // Schlüssel sind string und Werte int
 
anzahl_tage["Januar"] = 31; // Paar - Schlüssel(Monat) und Wert(Anzhal Tage)
anzahl_tage["Februar"]    = 28;
anzahl_tage["März"]  = 31;
anzahl_tage["April"]    = 30;
anzahl_tage["Mai"]    = 31;
anzahl_tage["Juni"]    = 30;
anzahl_tage["Juli"]    = 31;
anzahl_tage["August"]    = 31;
anzahl_tage["September"]    = 30;
anzahl_tage["Oktober"]    = 31;
anzahl_tage["November"]    = 30;
anzahl_tage["Dezember"]    = 31;
 
if (schaltjahr)
   anzahl_tage["Februar"] = 29; // wechseln Wert mit Schlüssel "Februar"
 
//Suche dem Schlüssel mit Methode "find"
if (anzahl_tage.find("März") == anzahl_tage.end())
    cout << "Schlüssel 'März' gibt es nicht in diese Tafel.";
else
    cout << "Anzahl Tage in März = " << anzahl_tage["März"];
</code>

==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.

<gallery widths="400" heights="300" perrow="2">
Bild:S3makrza_Kopiec_zupelny.jpg|Voll Heap
Bild:S3makrza_Kopiec_niezupelny.jpg|"Nicht" voll Heap
</gallery>

===Prioritätswarteschlangen auf Heap===

Auf Heap 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''
Mithilfe ''Insert'' können wir in erste freie Plätze das latzte Niveau hinzufügen und dann, wenn neue Element größer als seine Elternteil ist, können wir einander tauschen. Jetzt müssen wir überprüfen mit nächste Element in Hierarchie, und mit nächste... bis Wurzel.

<gallery widths="300" heights="300" perrow="3">
Bild:S3makrza_Kopiec_wstawianie11.jpg|1. Wir hinzufügen neu Element '17' in erste Plätze in Reihenfolge.
Bild:S3makrza_Kopiec_wstawianie2.jpg|2. 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.
Bild:S3makrza_Kopiec_wstawianie33.jpg|3. Machen wir das so lang (Bild 2), wenn größere Elternteil wir nicht finden, oder im Plätze Würzeln wechseln.
</gallery>



;''Delete Max''
Diese Operation löscht am gröbste Element (Wurzel) in unsere Baum. In neue leere Plätze geben wir die letzte (erst von recht Seite) Element auf unterste Niveau. Jetzt überprüfen wir mit "größere Kind" und wenn diese Kind größer ist, tauschen wir Plätzen diese 2 Elemente. Das machen wir so lang, wenn es keine größere Kinder gibt, oder diese Element ist Blatt.

<gallery widths="300" heights="300" perrow="2">
Bild:S3makrza_Kopiec_usuwanie1.jpg|1. Ganz normale Heap.
Bild:S3makrza_Kopiec_usuwanie2.jpg|2. Wir löschen am größte Element (18) und in diese Plätze nehmen die letzte (erst von recht Seite) Element auf unterste Niveau (13).
Bild:S3makrza_Kopiec_usuwanie3.jpg|3. Überprüfung mit am größten Kind - Element (13 <-> 17).
Bild:S3makrza_Kopiec_usuwanie4.jpg|4. So lang, wenn es schon keine Möglichkeiten gibt.
</gallery>