Basisklassen

Eine Prioritäten­liste (engl.: priority queue) ist eine abstrakte Daten­struktur zur Speicherung von Elementen aus einer geordneten Menge (M,  ≤ ), die folgende Operationen gestattet:

• Einfügen eines Eintrags
• Entfernen und Zurückgeben des größten Eintrags

In der Praxis bestehen die Elemente der Menge M und damit die Einträge in die Prioritäten­liste aus Paaren (k, x), wobei k ∈ ℝ die Priorität und x ein Verweis auf ein beliebiges Objekt ist. Die Ordnung der Elemente von M ergibt sich durch die Ordnung der Elemente von ℝ.

Bei Implementation einer Prioritäten­liste mit n Einträgen als unsortierte Liste ist das Einfügen eines Eintrags in konstanter Zeit möglich (durch Anhängen an die Liste), aber das Suchen des größten Eintrags benötigt Zeit Θ(n).

Bei Implementation als sortierte Liste ist das Ausgeben und Entfernen des größten Eintrags in konstanter Zeit möglich, aber das Einfügen eines Eintrags benötigt Zeit Θ(n) (eine verkettete Liste muss linear durchsucht werden, um den neuen Eintrag an die richtige Stelle einzusortieren, in einem Array müssen ggf. n Einträge verschoben werden, um den neuen Eintrag einzufügen).

Im Folgenden wird eine baumartige Daten­struktur angegeben, in der alle Operationen in Zeit O(log(n)) möglich sind, der Heap¹). Der Baum wird später als Array implementiert.

Mithilfe einer Prioritäten­liste lässt sich in einfacher Weise ein Sortier­verfahren realisieren:

1. Einfügen der n zu sortierenden Elemente in die Prioritäten­liste
2. Entfernen und Zurückgeben der n Elemente

Dadurch werden die Elemente in absteigender Reihenfolge zurück­gegeben. Mit einem Heap als zugrunde liegender Daten­struktur ergibt sich dann sogar ein optimales Sortier­verfahren mit der Zeit­komplexität O(n·log(n)), das Verfahren Heapsort.

Heap-Datenstruktur

Ein (fast) voll­ständiger binärer Baum T mit n Knoten hat die Tiefe d(T) = int(log(n)). Alle Teilbäume eines Heaps sind wiederum Heaps. Jedes Blatt ist ein Heap.

Heap-Operationen

Im Folgenden wird gezeigt, wie die das Einfügen eines Eintrags und das Entfernen und Zurückgeben des größten Eintrags in der Daten­struktur des Heaps realisiert werden können. Beide Operationen haben eine Zeit­komplexität von O(log(n)).

Einfügen eines Eintrags

Ein Eintrag k wird in den Heap eingefügt, indem ein neues Blatt v erzeugt und mit p(v) = k markiert wird. Dadurch hat aber der Vorgänger u dieses neuen Blattes v möglicherweise seine Heap-Eigenschaft verloren, nämlich wenn p(u) < p(v) ist. Durch Vertauschen dieser Markierungen erhält u seine Heap-Eigenschaft zurück, aber dadurch hat möglicherweise der Vorgänger von u seine Heap-Eigenschaft verloren usw.

Die Heap-Struktur lässt sich also wiederherstellen, indem der neu hinzugefügte Eintrag k so weit nach oben im Baum durchgetauscht wird, bis über ihm kein Eintrag  <  k mehr vorhanden ist. Dies ist spätestens an der Wurzel des Baumes der Fall.

Die Funktion upheap realisiert diese Wieder­herstellung der Heap-Struktur.

Prozedur upheap

Eingabe:

Heap mit neu hinzugefügtem Blatt v

Ausgabe:

wiederhergestellter Heap (durch Umordnung der Knotenmarken)

Methode:

1. solange v nicht die Wurzel ist wiederhole
1. setze u = Vorgänger von v
2. wenn p(u) ≥ p(v) dann
1. return
3. vertausche p(u) und p(v)
4. setze v = u

Entfernen und Zurückgeben des größten Eintrags

Die Markierung der Wurzel r ist der größte Eintrag. Dieser Eintrag wird zwischen­gespeichert. Dann wird die Markierung der Wurzel durch die Markierung des letzten Blattes über­schrieben; anschließend wird das letzte Blatt gelöscht. Die Wurzel des Baumes hat hierdurch möglicherweise ihre Heap-Eigenschaft verloren; der Baum ist ein Semi-Heap.

Ein Semi-Heap lässt sich zu einem Heap machen. Wenn die Markierung der Wurzel nicht die Heap-Eigenschaft hat, wird sie mit der größeren der beiden Nachfolger-Markierungen vertauscht. Dadurch hat die Wurzel wieder die Heap-Eigenschaft, aber der Nachfolger hat möglicherweise seine Heap-Eigenschaft verloren. Mit ihm wird dann in derselben Weise verfahren usw.

Die Markierung der Wurzel wird also so weit nach unten durchgetauscht, bis sie keinen größeren Knoten mehr unter sich hat. Dies ist spätestens an einem Blatt der Fall.

Die beschriebene Vorgehens­weise lässt sich als Prozedur wie folgt formulieren:

Prozedur downheap

Eingabe:

Semi-Heap mit Wurzel v

Ausgabe:

Heap (durch Umordnung der Knotenmarken)

Methode:

1. solange v kein Blatt ist wiederhole
1. wähle Nachfolgerknoten w mit maximaler Markierung a(w)
2. wenn p(v) ≥ p(w) dann
1. return
3. vertausche p(v) und p(w)
4. setze v = w

Implementierung

Ein (fast) voll­ständiger binärer Baum mit n Knoten lässt sich sehr elegant in einem Array speichern:

• die Wurzel steht an Position 0;
• die beiden Nachfolger des Knotens an Position v stehen an den Positionen 2v+1 und 2v+2.

Der Vorgänger eines Knotens an Position v ≠ 0 steht an Position (v-1) div 2. Alle Knoten an den Positionen 0, ..., n div 2 – 1 sind innere Knoten, alle Knoten an den Positionen  n div 2, ..., n – 1  sind Blätter (div bezeichnet die ganzzahlige Division).

Diese Darstellung des binären Baums in Form eines Arrays wird in der Implementierung der Prioritäten­liste als Klasse PriorityQueue verwendet.

Literatur

[CLRS 01]   T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms. 2. Auflage, The MIT Press (2001)

[Sed 88]   R. Sedgewick: Algorithms. 2. Auflage, Addison-Wesley (1988)