Robert Sedgewick: Algorithmen

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


11. Prioritätswarteschlangen



Heapsort

Auf der Basis der oben dargestellten grundlegenden Operationen mit Heaps kann eine elegante und effiziente Sortiermethode definiert werden. Diese Heapsort genannte Methode, verwendet keinen zusätzlichen Speicherplatz und garantiert, daß M Elemente in ungefähr M log M Schritten sortiert werden, unabhängig von den Eingabedaten. Leider ist ihre innere Schleife ein gutes Stück länger als die innere Schleife von Quicksort, und sie ist im Durchschnitt ungefähr halb so schnell wie Quicksort.

Die Idee besteht einfach darin, einen Heap aufzubauen, der die zu sortierenden Elemente enthält, und sie danach alle in der richtigen Reihenfolge zu entfernen. Im vorliegenden Abschnitt soll N weiterhin die Größe des Heap bezeichnen, daher verwenden wir M für die Anzahl der zu sortierenden Elemente. Eine Möglichkeit des Sortierens besteht darin, die construct-Operation zu implementieren, indem man M insert-Operationen ausführt, wie in den ersten beiden Zeilen des folgenden Programms, und danach M remove-Operationen, wobei das entfernte Element auf den Platz gesetzt wird, der von dem sich verkleinernden Heap gerade freigegeben wurde:

    N:=0;
    for k:=1 to M do insert(a[k]);
    for k:=M downto 1 do a[k]:=remove;

Dieses Programm bricht mit allen Regeln abstrakter Datenstrukturen, da es für die Prioritätswarteschlange eine spezielle Darstellung voraussetzt (während jeder Schleife befindet sich die Prioritätswarteschlange in a[1..k-1]), doch in diesem Falle ist das sinnvoll, da wir ein Sortierverfahren implementieren und keine Prioritätswarteschlange. Die Prozeduren für Prioritätswarteschlangen werden nur für beschreibende Zwecke verwendet; in einer realen Implementation des Sortierverfahrens könnten wir einfach den Code der Prozeduren verwenden, um unnötige Prozeduraufrufe zu vermeiden.

Abbildung 11.6 zeigt die Heaps, die aufgebaut werden, wenn die Schlüssel A S O R T I N G E X A M P L E in der angegebenen Reihenfolge in einen ursprünglich leeren Heap eingefügt werden; Abbildung 11.7 zeigt, wie diese Schlüssel sortiert werden, indem erst X entfernt wird, dann T usw.

Abbildung 11.6
Abbildung 11.6 Top-Down Konstruktion eines Heaps.

Abbildung 11.7
Abbildung 11.7 Sortieren aus einem Heap.

In Wirklichkeit ist es etwas besser, den Heap aufzubauen, indem man ihn rückwärts durchläuft und kleine Heaps von unten her erzeugt, wie Abbildung 11.8 zeigt. Bei dieser Methode wird jede Position im Feld als Wurzel eines kleinen Heaps betrachtet, und es wird die Tatsache ausgenutzt, daß downheap für solche kleinen Heaps ebenso gut arbeitet wie für den großen Heap. Indem der Heap rückwärts durchlaufen wird, ist jeder Knoten die Wurzel eines Heaps, für den die Heap-Bedingung erfüllt ist, außer möglicherweise für die Wurzel; mit downheap wird die Aufgabe vollendet. (Es ist nicht erforderlich, etwas mit Heaps der Größe 1 zu tun, daher beginnt das Durchlaufen auf halbem Wege rückwärts durch das Feld.)

Abbildung 11.8
Abbildung 11.8 Bottom-Up Konstruktion eines Heaps.

Wie wir bereits bemerkten, kann remove implementiert werden, indem zunächst das erste und das letzte Element vertauscht werden, dann N dekrementiert und schließlich downheap (1) aufgerufen wird. Dies führt zu der folgenden Implementation von Heapsort:

    procedure heapsort;
      var k,t: integer;
      begin
      N:=M;
      for k:=M div 2 downto 1 do downheap(k);
      repeat
        t:=a[1]; a[1]:=a[N]; a[N]:=t;
        N:=N-1; downheap(1)
      until N<=1;
    end;

Die ersten beiden Zeilen dieses Programms implementieren construct (M: integer), um einen Heap von M Elementen aufzubauen. (Wie soeben erwähnt wurde, bilden die Schlüssel in a[(M div 2)+1..M] jeweils Heaps aus einem Element, so daß sie trivialerweise der Heap-Bedingung genügen und nicht überprüft werden müssen.) Es ist interessant festzustellen, daß die Schleifen in diesem Programm, obwohl sie scheinbar sehr unterschiedliche Dinge realisieren, auf derselben grundlegenden Prozedur aufgebaut werden können.

Abbildung 11.9 veranschaulicht die Bewegung der Daten bei Heapsort, indem sie für unser Sortierbeispiel den Inhalt jedes von downheap bearbeiteten Heaps zeigt, unmittelbar nachdem downheap bewirkt hat, daß die Heap-Bedingung überall erfüllt ist.

Abbildung 11.9
Abbildung 11.9 Bewegungen der Daten bei Heapsort.

Eigenschaft 11.2 Bottom-Up Aufbau eines Heaps erfolgt in linearer Zeit.

Der Grund für diese Eigenschaft besteht darin, daß die meisten bearbeiteten Heaps klein sind. Um zum Beispiel einen Heap aus 127 Elementen aufzubauen, ruft die Methode downheap für (64 Heaps der Größe 1), 32 Heaps der Größe 3, 16 Heaps der Größe 7, 8 Heaps der Größe 15, 4 Heaps der Größe 31, 2 Heaps der Größe 63 und einen Heap der Größe 127 auf, so daß im ungünstigsten Falle 64 * 0 + 32 * 1 + 16& * 2 + 8 * 3 + 4 * 4 + 2 * 5 + 1 * 6 = 120 »Übertragungen« (doppelt so viele Vergleiche) benötigt werden. Für M = 2m ist eine obere Schranke für die Anzahl der Vergleiche durch

Formel

gegeben. Ein ähnlicher Beweis gilt, wenn M keine Zweierpotenz ist. w.z.b.w.

Diese Eigenschaft hat für Heapsort keine besondere Bedeutung, da dessen Laufzeit durch die M log M betragende Zeit für das Sortieren bestimmt wird. Sie ist jedoch für andere Anwendungen von Prioritätswarteschlangen wichtig, wo construct in linearer Zeit zu einem Algorithmus mit linearer Zeit führen kann. Beachten Sie, daß das Aufbauen eines Heaps mit M aufeinanderfolgenden Einfügungen (inserts) im ungünstigsten Fall M logM Schritte erfordert (obwohl es sich im Durchschnitt als linear erweist).

Eigenschaft 11.3 Heapsort benötigt für das Sortieren von M Elementen weniger als 2M lg M Vergleiche.

Eine etwas höhere Schranke, etwa 3M lg M, ergibt sich unmittelbar aus der Eigenschaft 11.1. Die hier angegebene Schranke erhält man aus sorgfältigeren Berechnungen unter Berücksichtigung der Eigenschaft 11.2. w.z.b.w.

Wie bereits erwähnt wurde, ist die Eigenschaft 11.3 der Hauptgrund dafür, daß Heapsort von praktischem Interesse ist: Die Anzahl der benötigten Schritte für das Sortieren von M Elementen ist für beliebige Eingabedaten garantiert proportional zu M log M. Im Unterschied zu den anderen Methoden, die wir kennengelernt haben, gibt es keine »ungünstigsten« Eingabedaten, bei denen Heapsort langsamer abläuft.

Abbildung 11.10
Abbildung 11.10 Sortieren einer zufälligen Permutation mittels Heapsort: Aufbauphase.

Die Abbildungen 11.10 und 11.11 zeigen die Arbeitsweise von Heapsort für eine größere zufällig angeordnete Datei. In Abbildung 11.10 scheint der Prozeß nichts mit Sortieren gemein zu haben, da große Elemente sich zum Beginn der Datei hin bewegen. Abbildung 11.11 zeigt dagegen, daß diese Struktur beibehalten wird, während die Datei sortiert wird, indem die großen Elemente weggenommen werden.

Abbildung 11.11
Abbildung 11.11 Sortieren einer zufälligen Permutation mittels Heapsort: Sortierphase.


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