Prioritätswarteschlange

Santus

Hallo erstmal,

ich möchte gerne eine Prioritätswarteschlange in C++ mit Hilfe eines Binär-Heaps schreiben. Ich stehe jetzt wie der Ochs vorm Berg. Die Klassen samt Konstruktoren und Destruktoren sind kein Problem. Aber mit der Implementierung des Heaps hapert es. Ich dachte daran, erst alle Elemente nach links unten einzuhängen und anschließen die Heap-Bedingung wieder herzustellen. Genau dort liegt mein Knackpunkt. Mir fallen Heaps und Bäume generell schwer. Wie genau stelle ich die Heap-Bedingung wieder her?

Die genaue Aufgabe lautet wie folgt:

Eine Prioritätswarteschlange ist eine Struktur ähnlich einer Queue. Im Gegensatz zu
einer Queue erhält aber jedes an die Warteschlange übergebene Datenelement eine
Priorität. Beim Abruf wird dann nicht das am längsten wartende Datenelement, sondern das Datenelement mit der höchsten Priorität zurückgeliefert.

Erstellen Sie eine Prioritätswarteschlange mit folgenden Eigenschaften:
• In der Warteschlange werden Gleitkommazahlen gespeichert
• Die Priorität ist eine beliebige ganze Zahl größer oder gleich 0.
• Die Daten werden in einem Array gehalten, der initial auf x Elemente ausgelegt ist.
• Reicht die Größe des Arrays nicht aus, so wird er um y Elemente vergrößert.
• Die Größen x und y können bei der Konstruktion der Warteschlange übergeben
werden. Alternativ werden die Defaultwerte x = 100 und y = 100 verwendet.

Erstellen Sie die Prioritätswarteschlange vollständig mit Konstruktor, Destruktor, Putund
Get-Methode sowie einer Methode, die prüft, ob die Warteschlange leer ist.
Erstellen Sie ein Anwendungsprogramm, das eine Prioritätswarteschlange instantiiert,
mit 1000 Werten unterschiedlicher Priorität füllt und die Werte anschließend wieder
abruft, bis die Warteschlange leer ist.

Geh zuerst einmal auf Wikipedia oder Google und mach dich Schlau was Heaps sind und wie man die Heap-Eigenschaften wiederherstellt.

Santus

Habe mir schon alles zu dem Thema bei Wikipedia durchgelesen.

Dort stand:

Die Basis aller Operationen bildet die Funktion heapify, die dazu dient, die Heap-Bedingung wiederherzustellen, wenn an einer beliebigen Position im Baum ein Element oder sein Schlüssel ausgetauscht wurde. Die Funktion heapify arbeitet in zwei Phasen. In der ersten Phase wird das Element, welches die Heap-Bedingung verletzt, solange nach oben geschoben, indem es seine Position mit dem Vater tauscht, bis es in der Wurzel steht oder der Schlüssel des Vaters kleiner als der des Elementes selbst ist. In der zweiten Phase wird das Element solange nach unten geschoben, indem es seine Position mit dem Kind tauscht, dessen Schlüssel am kleinsten ist, bis es Blatt ist oder die Kinder größere Schlüssel als das Element selbst besitzen.

So weit, so gut...

Hier mal meine "heapify":

void prioschlange::heaphealth(int k)
{
int j=k;

eintrag buf = heap[j];

while(heap[j].prio < heap[(j-1)/2].prio)
{
heap[j]=heap[(j-1)/2];
j = (j-1)/2;
heap[j]=buf;
}

while((heap[j].prio > heap[j*2+1].prio) || (heap[j].prio > heap[j*2+2].prio))
{
if(heap[j].prio > heap[j2+1].prio)
{
heap[j]=heap[j2+1];
j = j2+1;
heap[j]=buf;
}
if(heap[j].prio > heap[j2+2].prio)
{
heap[j]=heap[j2+1];
j = j2+2;
heap[j]=buf;
}
}
}

Das Ganze funktioniert allerdings vorne und hinten nicht.

Beim binären Heap ist heapify total trivial zu implementieren.
Du rufst die Funktion einfach mit dem Index auf und prüfst einfach ob das Element größer/kleiner als das linke Kind ist, wenn ja dann vertauschst du die beiden und rufst heapify erneut auf mit dem Index des linken Kindes. Für rechts gehts genau so.
Natürlich kann man es auch sehr einfach als Schleife realisieren, aber für dich dürfte die rekursive Implementierung fürs erste einfacher sein.

Santus

Danke für die Antwort. Hab es jetzt allerdings als stinknormale Queue (doppelt verkettete Liste) gelöst. Für die Bearbeitung der Aufgabe sollte das auch genügen. Auf die Frage nach der laufzeitoptimalen Lösung würde ich irgendeinen Baumstruktur vorschlagen.