Robert Sedgewick: Algorithmen

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


11. Prioritätswarteschlangen



Indirekte Heaps

Bei vielen Anwendungen von Prioritätswarteschlangen möchten wir die Datensätze überhaupt nicht verschieben. Stattdessen möchten wir, daß die Prioritätswarteschlangen-Routine nicht Werte zurückgibt, sondern uns sagt, welcher der Datensätze der größte ist usw. Dies ist mit der in Kapitel 8 beschriebenen Idee des »indirekten Sortierens« oder des »Pointer Sort« (Zeiger-Sortierens) vergleichbar. Eine Modifikation der obigen Programme dahingehend, daß sie in dieser Weise ablaufen, ist sehr einfach, jedoch manchmal verwirrend. Es lohnt sich, dies hier ausführlicher zu untersuchen, weil es so zweckmäßig ist, Heaps auf diese Art zu benutzen.

Wie in Kapitel 8 arbeiten die Prioritätswarteschlangen-Routinen, anstatt die Schlüssel im Feld a umzuordnen, mit einem Feld p von Indizes, die sich auf das Feld a beziehen. a[p[k]] ist somit der Datensatz, der dem k-ten Element des Heap entspricht, für k zwischen 1 und N. (Wir setzen nach wie vor Datensätze von aus einem Wort bestehenden Schlüsseln voraus; wie in Kapitel 8 besteht ein wesentlicher Vorteil dann darin, daß wir leicht zu komplizierteren Datensätzen und Schlüsseln übergehen können.) Darüber hinaus möchten wir ein weiteres Feld q zur Verfügung haben, in dem die Heap-Position des k-ten Elements des Feldes gespeichert wird. Damit ermöglichen wir die change- und delete-Operationen. Folglich ist der Eintrag von q für das größte Element im Feld die Zahl 1 usw. Wenn wir zum Beispiel den Wert von a[k] verändern wollten, könnten wir seine Heap-Position in q[k] finden und upheap oder downheap benutzen. In Abbildung 11.12 sind die Werte in diesen Feldern für unser Beispiel eines Heaps angegeben; wir bemerken, daß p[q[k]] = q[p[k]] = k für alle k von 1 bis N gilt.

Abbildung 11.12
Abbildung 11.12 Indirekte Heap-Datenstrukturen.

Wir beginnen mit p[k] = q[k] = k für k von 1 bis N, was besagt, daß kein Umordnen erfolgt ist. Das Programm für das Aufbauen des Heap sieht fast genauso aus wie zuvor:

    procedure pqconstruct;
      var k: integer;
      begin
      N:=M;
      for k:=1 to N do
        begin p[k]:=k; q[k]:=k end;
      for k:=M div 2 downto 1 do pqdownheap(k);
      end;
(Wir versehen Implementationen von Prioritätswarteschlangen-Routinen, die auf indirekten Heaps beruhen, mit dem Präfix »pq«, um sie in späteren Kapiteln leichter identifizieren zu können.)

Um nunmehr downheap so zu modifizieren, daß es indirekt arbeitet, brauchen wir nur die Stellen zu betrachten, wo auf a Bezug genommen wird. Wo zuvor ein Vergleich vorgenommen wurde, muß nun ein indirekter Zugriff auf a über p erfolgen. Wo zuvor eine Bewegung erfolgte, muß nunmehr die Bewegung in p und nicht in a realisiert werden, und q muß dementsprechend geändert werden. Dies führt zu der folgenden Implementation:

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

Die anderen oben angegebenen Prozeduren können auf ähnliche Weise modifiziert werden, um »pqinsert«, »pqchange« usw. zu implementieren.

Es kann eine ähnliche indirekte Implementation entwickelt werden, die darauf beruht, daß p als ein Feld von Zeigern gespeichert wird, die auf getrennt angeordnete Datensätze weisen. In diesem Falle ist etwas mehr Mühe erforderlich, um die Funktion von q zu implementieren (Auffinden der Heap-Position bei gegebenem Datensatz).


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