Robert Sedgewick: Algorithmen

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


11. Prioritätswarteschlangen



Algorithmen mit Heaps

Die Algorithmen für Prioritätswarteschlangen unter Verwendung von Heaps laufen alle in der Weise ab, daß sie zuerst eine einfache Strukturänderung vornehmen, welche die Heap-Bedingung verletzen könnte, und anschließend den Heap durchlaufen und ihn so modifizieren, daß die Erfüllung der Heap-Bedingung überall gewährleistet ist. Einige der Algorithmen durchlaufen den Heap von der untersten Ebene zur Spitze, andere von der Spitze nach unten. Bei allen Algorithmen setzen wir voraus, daß die Datensätze aus einem Wort bestehende ganzzahlige Schlüssel sind, die in einem Feld a von einer gewissen maximalen Größe gespeichert sind, wobei die aktuelle Größe des Heaps in einer ganzen Zahl N gespeichert ist. Wir bemerken, daß N ebenso ein Teil der Definition des Heaps ist wie die Schlüssel und Datensätze selbst.

Um in der Lage zu sein, einen Heap aufzubauen, ist es zunächst erforderlich, die Operation insert zu implementieren. Da sich durch diese Operation die Größe des Heaps um eins erhöht, muß N inkrementiert werden. Danach wird der einzufügende Datensatz in a[N] abgelegt; dies kann zur Verletzung der Heap-Bedingung führen. Falls die Heap-Bedingung verletzt ist (der neue Knoten ist größer als sein Vorgänger), so kann die Verletzung rückgängig gemacht werden, indem der neue Knoten mit seinem Vorgänger ausgetauscht wird. Dies kann erneut eine Verletzung verursachen, die wieder auf die gleiche Weise korrigiert werden kann. Wenn zum Beispiel P in den obigen Heap eingefügt werden soll, wird es zuerst in a[N] als der rechte Nachfolger von M gespeichert. Danach wird es mit M ausgetauscht, da es größer als M ist, und mit O ausgetauscht, da es größer als O ist; da es kleiner als X ist, ist der Prozeß damit beendet. Es ergibt sich der in der Abbildung 11.3 dargestellte Heap.

Abbildung 11.3
Abbildung 11.3 Einfügen eines neuen Elements (P) in einen Heap.

Das Programm für diese Methode ist sehr einfach. In der untenstehenden Implementation fügt insert ein neues Element in a[N] ein und ruft dann upheap (N) auf, um die Verletzung der Heap-Bedingung in N zu korrigieren:

    procedure upheap(k: integer);
      var v: integer;
      begin
      v:=a[k]; a[0]:=maxint;
      while a[k div 2]<=v do
        begin a[k]:=a[k div 2]; k:=k div 2 end;
      a[k]:=v
      end;
    procedure insert(v: integer);
      begin
      N:=N+1; a[N]:=v;
      upheap(N)
    end;

Würde k div 2 überall in diesem Programm durch k-1 ersetzt, so läge dem Wesen ein Schritt von Insertion Sort vor (Implementieren einer Prioritätswarteschlange mittels einer geordneten Liste); hier realisieren wir stattdessen ein »Einfügen« des neuen Schlüssels längs des Pfades von N zur Wurzel. Wie bei Insertion Sort ist es nicht notwendig, einen vollständigen Austausch innerhalb der Schleife vorzunehmen, da v stets an den Austauschoperationen beteiligt ist. Ein Marken-Schlüssel muß in a[0] gesetzt werden, um die Schleife abzubrechen, falls v größer ist als alle Schlüssel im Heap.

Die replace-Operation erfordert das Ersetzen des Schlüssels bei der Wurzel durch einen neuen Schlüssel und danach die Bewegung im Heap von oben nach unten, um die Heap-Bedingung wieder herzustellen. Wenn zum Beispiel das X im obigen Heap durch C ersetzt werden soll, so besteht der erste Schritt darin, C an der Wurzel zu speichern. Dadurch wird die Heap-Bedingung verletzt. Die Verletzung kann korrigiert werden, indem C mit T, dem größeren der beiden Nachfolger der Wurzel, ausgetauscht wird. Hierdurch wird eine Verletzung auf der nächstfolgenden Ebene verursacht, die wiederum korrigiert werden kann, indem C mit dem größeren seiner beiden Nachfolger (in diesem Falle S) ausgetauscht wird. Der Prozeß setzt sich so lange fort, bis die Heap-Bedingung an dem durch C besetzten Knoten nicht mehr verletzt ist. Im Beispiel legt C den gesamten Weg bis zur untersten Ebene des Heaps zurück, wobei sich der in Abbildung 11.4 dargestellte Heap ergibt.

Abbildung 11.4
Abbildung 11.4 Ersetzen des größten Schlüssels in einem Heap (durch C).

Die Operation »remove the largest« (Entfernen des größten Elements) erfordert nahezu den gleichen Prozeß. Da der Heap nach der Operation ein Element weniger haben wird, ist es erforderlich, N zu dekrementieren, so daß kein Platz für das Element bleibt, das auf der letzten Position gespeichert war. Doch das größte Element (das sich in a[1] befindet) soll entfernt werden, und damit entspricht die Operation remove der Operation replace unter Verwendung des Elements, das sich in a[N] befand. Der in Abbildung 11.5 dargestellte Heap ist das Ergebnis des Entfernens von T aus dem Heap Abbildung 11.4, indem dieses durch M ersetzt wurde und letzteres dann unter Verwendung des größeren der beiden Nachfolger nach unten bewegt wurde, bis ein Knoten erreicht wurde, dessen beide Nachfolger kleiner als M sind.

Abbildung 11.5
Abbildung 11.5 Entfernen des größten Elements aus einem Heap.

Im Mittelpunkt der Implementation dieser beiden Operationen steht der Prozeß der Korrektur eines Heap, in dem die Heap-Bedingung überall erfüllt ist, außer möglicherweise an der Wurzel. Wenn der Schlüssel an der Wurzel zu klein ist, muß er im Heap nach unten bewegt werden, ohne daß dabei die Heap-Bedingung bei irgendeinem der berührten Knoten verletzt wird. Es zeigt sich, daß die gleiche Operation angewandt werden kann, um den Heap zu korrigieren, nachdem der Wert eines beliebigen Eintrags verkleinert worden ist. Sie kann wie folgt implementiert werden:

    procedure downheap(k: integer);
        label 0;
        var i,j,v: integer;
        begin
        v:=a[k];
        while k<=N div 2 do
          begin
          j:=k+k;
          if j<N then if a[j]<a[j+1] then j:=j+1;
          if v>=a[j] then goto 0;
          a[k]:=a[j]; k:=j;
          end;
     0: a[k]:=v
        end;

Diese Prozedur bewegt sich im Heap nach unten, wobei der Knoten auf Position k, falls erforderlich, mit dem größeren seiner beiden Nachfolger ausgetauscht wird. Dieser Prozeß bricht ab, wenn der Knoten auf Position k größer ist als beide Nachfolger oder wenn die unterste Ebene erreicht ist. (Es ist anzumerken, daß es möglich ist, daß der Knoten auf Position k nur einen Nachfolger hat; dieser Fall muß entsprechend behandelt werden!) Wie oben ist ein vollständiger Austausch nicht notwendig, da v stets an den Austauschoperationen beteiligt ist. Die innere Schleife in diesem Programm ist ein Beispiel für eine Schleife, die wirklich zwei verschiedene Ausgänge hat: einen für den Fall, daß die unterste Ebene des Heap erreicht wird (wie im ersten Beispiel oben), und einen weiteren für den Fall, daß die Heap-Bedingung irgendwo im Inneren des Heap erfüllt wird. Die goto-Anweisung könnte mit einigem Aufwand und bei einem gewissen Verlust an Übersichtlichkeit vermieden werden.

Nunmehr ist die Implementation der remove-Operation eine direkte Anwendung dieser Prozedur:

    function remove: integer;
      begin
      remove:=a[1];
      a[1]:=a[N]; N:=N-1;
      downheap(1);
      end;
Der zurückgegebene Wert ergibt sich aus a[1]; danach wird das Element von a[N] auf a[1] gesetzt und die Größe des Heap dekrementiert, wonach nur noch ein Aufruf von downheap erforderlich ist, um die Heap-Bedingung überall zu erfüllen.

Die Implementation der replace-Operation ist nur unwesentlich komplizierter:

    function replace(v: integer):integer;
      begin
      a[0]:=v;
      downheap(0);
      replace:=a[0];
      end;

Dieses Programm verwendet a[0] auf eine künstliche Weise: Seine Nachfolger sind 0 (es selbst) und 1, so daß der Heap nicht berührt wird, wenn v größer als das größte Element im Heap ist; andernfalls wird v im Heap abgelegt, und a[1] wird zurückgegeben.

Die delete-Operation für ein beliebiges Element aus dem Heap und die change-Operation können gleichfalls unter Anwendung einer einfachen Kombination der obigen Methoden implementiert werden. Wenn zum Beispiel die Priorität des Elements auf Position k erhöht wird, kann upheap (k) aufgerufen werden, und wenn sie verkleinert wird, erfüllt downheap (k) die Aufgabe.

Eigenschaft 11.1 Alle grundlegenden Operationen insert, remove, replace, (downheap und upheap), delete und change erfordern weniger als 2 lg N Vergleiche, wenn sie für einen Heap mit N Elementen ausgeführt werden.

Alle diese Operationen beinhalten eine Bewegung längs eines Pfades zwischen der Wurzel und der untersten Ebene des Heap, welcher für einen Heap der Größe N nicht mehr als lg N Elemente umfaßt. Der Faktor 2 entsteht durch downheap, welches in seiner inneren Schleife zwei Vergleiche ausführt; die anderen Operationen erfordern nur lg N Vergleiche. w.z.b.w.

Man beachte, daß die join-Operation in dieser Aufzählung nicht enthalten ist. Eine effiziente Ausführung dieser Operation scheint eine wesentlich kompliziertere Datenstruktur zu erfordern. Andererseits ist in vielen Anwendungsfällen zu erwarten, daß diese Operation weit seltener benötigt wird als die anderen.


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