Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


11. Prioritätswarteschlangen



Elementare Implementationen

Eine Methode der Organisation einer Prioritätswarteschlange ist eine ungeordnete Liste, wobei die Elemente einfach in einem Feld a[1..N] aufbewahrt werden, ohne die Schlüssel zu beachten. Folglich ist construct bei dieser Organisation nicht notwendig, doch insert und remove lassen sich leicht wie folgt implementieren:

    procedure insert(v: integer);
      begin
      N:=N+1; a[N]:=v;
      end;
    function remove: integer;
      var j,max: integer;
      begin
      max:=1;
      for j:=2 to N do
        if a[j]>a[max] then max:=j;
      remove:=a[max];
      a[max]:=a[N]; N:=N-1;
      end;

Für insert inkrementieren wir einfach N und legen das neue Element in a[N] ab, wobei für diese Operation eine konstante Zeit benötigt wird. Remove erfordert dagegen das Durchsuchen des Feldes, um das Element mit dem größten Schlüssel zu finden, wofür eine lineare Zeit benötigt wird (alle Elemente im Feld müssen betrachtet werden), danach das Vertauschen von a[N] mit dem Element mit dem größten Schlüssel und das Dekrementieren von N. Die Implementation von replace sähe ganz ähnlich aus und wird daher nicht angegeben.

Um die Operation change zu implementieren (Verändern der Priorität des Elements in a[k]), können wir einfach den neuen Wert speichern, und um das Element in a[k] zu löschen (delete), können wir es, wie in der letzten Zeile von remove, mit a[N] vertauschen und N dekrementieren. (In Kapitel 3 sahen wir, daß Operationen, die sich auf einzelne Datenelemente beziehen, nur in einer Implementation »mit Zeigern« oder »indirekten« Implementation sinnvoll sind. Dabei wird für jedes Element ein Verweis auf seine tatsächliche Position in der Datenstruktur verwaltet.)

Eine andere elementare Form der Organisation, die benutzt werden kann, ist eine geordnete Liste, wobei wiederum ein Feld a[1..N] verwendet wird, die Elemente jedoch entsprechend der wachsenden Reihenfolge ihrer Schlüssel aufbewahrt werden. Nunmehr erfordert remove einfach das Zurückgeben von a[N] und das Dekrementieren von N (eine Operation, die in konstanter Zeit ausgeführt wird), insert dagegen erfordert das Bewegen der größeren Elemente im Feld um eine Position nach rechts, wofür eine lineare Zeit benötigt werden könnte.

Jeder Algorithmus für Prioritätswarteschlangen kann in einen Sortieralgorithmus umgewandelt werden, indem wiederholt insert benutzt wird, um eine Prioritätswarteschlange zu erzeugen, die alle zu sortierenden Elemente enthält, und indem danach wiederholt remove benutzt wird, um die Prioritätswarteschlange zu leeren, wobei die Elemente in umgekehrter Reihenfolge erhalten werden. Die Benutzung einer als ungeordnete Liste dargestellten Prioritätswarteschlange entspricht somit Selection Sort, und die Verwendung einer geordneten Liste entspricht Insertion Sort.

Anstelle der oben angegebenen Implementation mit Hilfe eines Feldes können auch verkettete Listen für die ungeordnete Liste oder die geordnete Liste verwendet werden. Dies ändert nichts an den grundlegenden Merkmalen der Leistungsfähigkeit für insert, remove oder replace, gibt jedoch die Möglichkeit, delete und join in konstanter Zeit auszuführen. Auf diese Implementationen wird hier verzichtet, da sie den in Kapitel 3 angegebenen grundlegenden Listenoperationen so ähnlich sind und da Implementationen ähnlicher Methoden für das Suchproblem (Finden eines Datensatzes mit einem gegebenen Schlüssel) in Kapitel 14 angegeben werden.

Meistens lohnt es sich, sich diese einfachen Implementationen zu merken, da sie in vielen praktischen Situationen komplizierteren Methoden überlegen sein können. Zum Beispiel könnte die Implementation mittels einer ungeordneten Liste in einer Anwendung geeignet sein, wo nur einige wenige remove-Operationen, jedoch sehr viele Einfügungen ausgeführt werden, während eine geordnete Liste geeignet wäre, wenn bei den einzufügenden Elementen immer zu erwarten ist, daß sie dem größten Element in der Prioritätswarteschlange nahekommen.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]