Prioritätenliste

 aufwärts

Eine Prioritätenliste (engl.: priority queue) ist eine abstrakte Datenstruktur zur Speicherung von Elementen aus einer geordneten Menge (M, kleiner gleich), die folgende Operationen gestattet:

In der Praxis bestehen die Elemente der Menge M und damit die Einträge in die Prioritätenliste aus Paaren (k, x), wobei k Element reelle Zahlen 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 reelle Zahlen.

Bei Implementation einer Prioritätenliste 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 Datenstruktur angegeben, in der alle Operationen in Zeit O(log(n)) möglich sind, der Heap1). Der Baum wird später als Array implementiert.

Mithilfe einer Prioritätenliste lässt sich in einfacher Weise ein Sortierverfahren realisieren:

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

Dadurch werden die Elemente in absteigender Reihenfolge zurückgegeben. Mit einem Heap als zugrundeliegender Datenstruktur ergibt sich dann sogar ein optimales Sortierverfahren mit der Zeitkomplexität O(n·log(n)), das Verfahren Heapsort.

Heap-Datenstruktur

Definition:  Sei T = (V, E) ein (fast) vollständiger binärer Baum mit einer Knotenmarkierung p : V Pfeil nach rechts M, die jedem Knoten u eine Markierung p(u) aus der geordneten Menge (M, kleiner gleich) zuordnet.

Ein Knoten v Element V hat die Heap-Eigenschaft, wenn er keinen direkten Nachfolgerknoten mit einer größeren Markierung hat, oder anders ausgedrückt, wenn gilt:

 für alle w Element V  :  (v, wElement E  folgt  p(vgrößer gleich p(w)

T heißt Heap, wenn alle Knoten die Heap-Eigenschaft haben, d.h. wenn gilt:

 für alle (v, wElement E  :  p(vgrößer gleich p(w)

Wir nennen T einen Semi-Heap, wenn alle Knoten außer möglicherweise der Wurzel r die Heap-Eigenschaft haben, d.h. wenn gilt:

 für alle (v, wElement E  :  v ≠ r  folgt  p(vgrößer gleich p(w)

Beispiel:  

Bild 1: Heap mit 10 Knoten
Bild 1: Heap mit 10 Knoten

Ein (fast) vollstä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 Datenstruktur des Heaps realisiert werden können. Beide Operationen haben eine Zeitkomplexitä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 Wiederherstellung 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)größer gleichp(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 zwischengespeichert. Dann wird die Markierung der Wurzel durch die Markierung des letzten Blattes überschrieben; 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 Vorgehensweise 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)größer gleichp(w) dann
      1. return
    3. vertausche p(v) und p(w)
    4. setze v = w

 

Implementierung

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

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).

Array-Repräsentation eines Heaps
Bild 2: Array-Repräsentation des Heaps von Bild 1

Diese Darstellung des binären Baums in Form eines Arrays wird in der Implementierung der Prioritätenliste 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)

1)  Der Begriff Heap (deutsch: Haufen) bezeichnet einerseits die hier verwendete Datenstruktur, andererseits auch den Speicherbereich für dynamische Variablen im Rechner – zwei unterschiedliche Bedeutungen desselben Wortes.

 

Weiter mit:   [Implementierung]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 25.02.1997   Updated: 29.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik