Lektion 2.6

Heaps und Prioritätswarteschlangen

45 min Lesezeit
Lesen anpassen

Nach dieser Lektion kannst du

  • die Prioritätswarteschlange als abstrakten Datentyp beschreiben und Umsetzungen nach Laufzeit vergleichen,

  • einen binären Heap als Array lesen und Eltern- und Kindindizes berechnen,

  • Einfügen mit Aufsteigen und Entnehmen des Minimums mit Versickern von Hand ausführen,

  • beweisen, dass der Aufbau eines Heaps aus nn Zahlen nur O(n)O(n) kostet,

  • Heapsort erklären und Anwendungen wie Dijkstras Algorithmus und Ereignissimulation einordnen.

Vorausgesetzt: Stapel und Warteschlangen, Binäre Suchbäume, AVL-Bäume: balancierte Suchbäume, Laufzeit messen: Operationen zählen und O-Notation

In einer Notaufnahme wird nicht der behandelt, der zuerst kam, sondern der, dem es am schlechtesten geht. Ständig kommen Menschen hinzu, jeder bekommt eine Dringlichkeitsstufe, und sobald ein Behandlungsplatz frei wird, ist die Frage: Wer ist jetzt am dringendsten? Eine gewöhnliche Warteschlange (wer zuerst kommt, kommt zuerst dran) hilft hier nicht.

Mit einer unsortierten Liste ist das Hinzufügen billig, O(1)O(1), aber für die Frage nach dem Dringendsten muss man alle nn Einträge ansehen. Eine sortierte Liste liefert den Dringendsten sofort, aber jedes Einfügen sucht erst die richtige Stelle, im schlechtesten Fall O(n)O(n). Ein AVL-Baum schafft beides in O(log⁡n)O(\log n), braucht dafür aber Verweise, Höhen und Rotationen, obwohl wir nie einen beliebigen Schlüssel suchen.

Es geht einfacher. Man verlangt nur eine schwache Ordnung: Die Einträge bilden einen Baum, und jeder Eintrag ist mindestens so dringend wie alle direkt unter ihm. Dann steht der dringendste ganz oben, der Rest darf ungeordnet sein. Und der Baum lässt sich ohne einen einzigen Verweis in einem Array ablegen.

Vermute zuerst

In einem Binärbaum ist jeder Schlüssel höchstens so groß wie die Schlüssel seiner Kinder. Alle Schlüssel sind verschieden, das Minimum steht an der Wurzel. Wo steht der zweitkleinste Schlüssel?

Definition

Prioritätswarteschlange

Eine Prioritätswarteschlange ist ein abstrakter Datentyp: Er legt fest, welche Operationen es gibt, nicht wie sie umgesetzt sind. Sie verwaltet eine Menge von Einträgen mit Schlüsseln (Prioritäten, kleiner heißt dringender) und bietet:

  • einfuegen(x)\texttt{einfuegen(x)}: Eintrag xx hinzufügen.
  • min()\texttt{min()}: einen Eintrag mit kleinstem Schlüssel zurückgeben, ohne ihn zu entfernen.
  • extrahiereMin()\texttt{extrahiereMin()}: einen Eintrag mit kleinstem Schlüssel zurückgeben und entfernen.
  • istLeer()\texttt{istLeer()}: prüfen, ob noch Einträge da sind.

Gleiche Schlüssel sind erlaubt. Viele Umsetzungen bieten zusätzlich verringereSchluessel\texttt{verringereSchluessel}, das den Schlüssel eines Eintrags verkleinert, ihn also dringender macht.

Beispiel

Umsetzungen im Vergleich

Schlechteste Laufzeiten bei nn Einträgen:

UmsetzungeinfuegenminextrahiereMin
unsortiertes ArrayO(1)O(1) amortisiertO(n)O(n)O(n)O(n)
sortiertes Array (absteigend)O(n)O(n)O(1)O(1)O(1)O(1)
AVL-BaumO(log⁡n)O(\log n)O(log⁡n)O(\log n)O(log⁡n)O(\log n)
binärer HeapO(log⁡n)O(\log n)O(1)O(1)O(log⁡n)O(\log n)

Beim sortierten Array steht das Minimum am Ende, damit das Entfernen nichts verschieben muss. „Amortisiert“ beim unsortierten Array bezieht sich auf das gelegentliche Vergrößern des Arrays. Der binäre Heap erreicht die Laufzeit des AVL-Baums ohne Verweise und Rotationen und kann aus nn Zahlen in nur O(n)O(n) aufgebaut werden.

Definition

Vollständiger Binärbaum im Array

Ein Binärbaum mit nn Knoten heißt hier vollständig, wenn alle Ebenen bis auf die unterste ganz gefüllt sind und die unterste von links lückenlos gefüllt ist. Nummeriert man die Knoten ebenenweise von oben nach unten und in jeder Ebene von links nach rechts mit 0,1,…,n−10, 1, \dots, n-1, kann man den Baum in einem Array A[0..n−1]A[0..n-1] ablegen. Für den Knoten mit Index ii gilt dann:

  • linkes Kind: 2i+12i + 1, rechtes Kind: 2i+22i + 2, soweit diese Zahl kleiner als nn ist,
  • Elternknoten (für i≥1i \ge 1): ⌊(i−1)/2⌋\lfloor (i-1)/2 \rfloor.

Dabei ist ⌊t⌋\lfloor t \rfloor die größte ganze Zahl ≤t\le t. Ein Knoten ist genau dann ein Blatt, wenn 2i+1≥n2i + 1 \ge n, also i≥⌊n/2⌋i \ge \lfloor n/2 \rfloor: Die hintere Hälfte des Arrays besteht aus Blättern.

Warum die Formel stimmt: Ebene dd hat die Indizes 2d−12^d - 1 bis 2d+1−22^{d+1} - 2. Steht ii an Stelle jj seiner Ebene, also i=2d−1+ji = 2^d - 1 + j, dann stehen vor seinen Kindern in Ebene d+1d+1 genau 2j2j Knoten, und das linke Kind hat den Index 2d+1−1+2j=2i+12^{d+1} - 1 + 2j = 2i + 1.

Definition

Heap-Eigenschaft

Ein Array A[0..n−1]A[0..n-1] ist ein Min-Heap, wenn für jeden Index i≥1i \ge 1 gilt:

A[⌊(i−1)/2⌋]≤A[i]A[\lfloor (i-1)/2 \rfloor] \le A[i],

also jeder Elternknoten höchstens so groß wie seine Kinder ist. Beim Max-Heap steht ≥\ge. Wir arbeiten mit Min-Heaps; alles gilt spiegelbildlich für Max-Heaps.

IndexSchlüsselElternindexlinkes Kindrechtes Kind
02–12
14034
23056
3717–
451––
592––
662––
783––

Das ist der Min-Heap E=[2,4,3,7,5,9,6,8]E = [2, 4, 3, 7, 5, 9, 6, 8]. Er ist nicht sortiert: 44 steht vor 33. Jede Elternzeile ist aber höchstens so groß wie die Kinderzeilen.

Gegenbeispiel: [1,4,2,3,6,5][1, 4, 2, 3, 6, 5] ist kein Min-Heap. Index 33 (Schlüssel 33) hat den Elternindex 11 mit Schlüssel 4>34 > 3.

Satz

Minimum an der Wurzel, Höhe logarithmisch

In einem Min-Heap mit n≥1n \ge 1 Einträgen steht ein kleinster Schlüssel in A[0]A[0], und die Höhe des Baums ist ⌊log⁡2n⌋\lfloor \log_2 n \rfloor.

Kurz geprüft

Welchen Schlüssel hat im Heap E=[2,4,3,7,5,9,6,8]E = [2, 4, 3, 7, 5, 9, 6, 8] der Elternknoten des Index 66?

Beispiel

Einfügen: Aufsteigen

Der neue Eintrag kommt an die erste freie Stelle A[n]A[n]; der Baum bleibt vollständig. Ist er kleiner als sein Elternknoten, ist nur dort die Heap-Eigenschaft verletzt. Man tauscht ihn so lange mit dem Elternknoten, bis dieser nicht größer ist oder er die Wurzel erreicht.

ZeileEinrückungAnweisung
10einfuegen(x):\texttt{einfuegen(x):}
21A[n] = x\texttt{A[n] = x}
31n = n + 1\texttt{n = n + 1}
41aufsteigen(n - 1)\texttt{aufsteigen(n - 1)}
50aufsteigen(i):\texttt{aufsteigen(i):}
61while i > 0 and A[eltern(i)] > A[i]:\texttt{while i > 0 and A[eltern(i)] > A[i]:}
72vertausche(A, i, eltern(i))\texttt{vertausche(A, i, eltern(i))}
82i = eltern(i)\texttt{i = eltern(i)}

Dabei ist eltern(i)=⌊(i−1)/2⌋\texttt{eltern(i)} = \lfloor (i-1)/2 \rfloor. Beispiel: 11 in E=[2,4,3,7,5,9,6,8]E = [2, 4, 3, 7, 5, 9, 6, 8] einfügen.

SchrittiiVergleichArray danach
anhängen8–[2, 4, 3, 7, 5, 9, 6, 8, 1]
18A[3]=7>1A[3] = 7 > 1, tauschen[2, 4, 3, 1, 5, 9, 6, 8, 7]
23A[1]=4>1A[1] = 4 > 1, tauschen[2, 1, 3, 4, 5, 9, 6, 8, 7]
31A[0]=2>1A[0] = 2 > 1, tauschen[1, 2, 3, 4, 5, 9, 6, 8, 7]
Ende0Wurzel erreicht[1, 2, 3, 4, 5, 9, 6, 8, 7]

Jeder Tausch geht eine Ebene hinauf, also höchstens ⌊log⁡2n⌋\lfloor \log_2 n \rfloor Tausche: O(log⁡n)O(\log n). Korrekt ist es, weil der aufsteigende Eintrag beim Tauschen kleiner als der alte Elternknoten ist, der damit auch zu seinem neuen Kind passt, und weil der alte Elternknoten schon vorher höchstens so groß war wie seine übrigen Nachkommen.

Beispiel

Minimum entnehmen: Versickern

Das Minimum steht in A[0]A[0]. Man ersetzt es durch den letzten Eintrag und verkleinert nn. Jetzt ist höchstens an der Wurzel etwas verletzt. Der Eintrag versickert: Er wird mit dem kleineren seiner Kinder getauscht, solange dieses kleiner ist.

ZeileEinrückungAnweisung
10extrahiereMin():\texttt{extrahiereMin():}
21m = A[0]\texttt{m = A[0]}
31n = n - 1\texttt{n = n - 1}
41A[0] = A[n]\texttt{A[0] = A[n]}
51versickern(0)\texttt{versickern(0)}
61return m\texttt{return m}
70versickern(i):\texttt{versickern(i):}
81while 2*i + 1 < n:\texttt{while 2*i + 1 < n:}
92k = 2*i + 1\texttt{k = 2*i + 1}
102if k + 1 < n and A[k + 1] < A[k]: k = k + 1\texttt{if k + 1 < n and A[k + 1] < A[k]: k = k + 1}
112if A[i] <= A[k]: return\texttt{if A[i] <= A[k]: return}
122vertausche(A, i, k)\texttt{vertausche(A, i, k)}
132i = k\texttt{i = k}

Beispiel mit E=[2,4,3,7,5,9,6,8]E = [2, 4, 3, 7, 5, 9, 6, 8]: Entnommen wird 22, die 88 kommt an die Wurzel.

SchrittiiKinderArray danach
ersetzen0–[8, 4, 3, 7, 5, 9, 6]
10A[1]=4A[1] = 4, A[2]=3A[2] = 3; kleiner ist 3<83 < 8, tauschen[3, 4, 8, 7, 5, 9, 6]
22A[5]=9A[5] = 9, A[6]=6A[6] = 6; kleiner ist 6<86 < 8, tauschen[3, 4, 6, 7, 5, 9, 8]
Ende6keine Kinder[3, 4, 6, 7, 5, 9, 8]

Je Ebene höchstens zwei Vergleiche und ein Tausch, also O(log⁡n)O(\log n). Das neue Minimum 33 war ein Kind der alten Wurzel, wie in der Vermutung oben.

Häufige Fehler

Mit dem falschen Kind tauschen

Beim Versickern wird oft mit dem linken Kind getauscht, oder mit irgendeinem Kind, das kleiner ist. Im Beispiel: Die 88 an der Wurzel hat die Kinder 44 und 33. Tauscht man mit der 44, steht 44 an der Wurzel und hat das Kind 3<43 < 4. Die Heap-Eigenschaft ist verletzt, und min()\texttt{min()} liefert 44 statt 33.

Richtig ist

Immer mit dem kleineren der beiden Kinder tauschen (Zeile 10). Dann ist der neue Elternknoten höchstens so groß wie beide Kinder, auch wie das Geschwister, das nicht getauscht wurde. Beim Max-Heap entsprechend mit dem größeren.

Kurz geprüft

Aus dem Heap [1,3,2,5,9,8][1, 3, 2, 5, 9, 8] wird das Minimum entnommen. Wie sieht das Array danach aus?

Satz

Aufbau eines Heaps in O(n)O(n)

Ein beliebiges Array A[0..n−1]A[0..n-1] wird zum Min-Heap, wenn man von hinten nach vorn jeden inneren Knoten versickern lässt (die Blätter ab Index ⌊n/2⌋\lfloor n/2 \rfloor sind schon Heaps aus einem Element):

ZeileEinrückungAnweisung
10aufbauen(A, n):\texttt{aufbauen(A, n):}
21for i = n div 2 - 1 down to 0:\texttt{for i = n div 2 - 1 down to 0:}
32versickern(i)\texttt{versickern(i)}

(div\texttt{div} ist die ganzzahlige Division.) Dieser Aufbau braucht weniger als 4n4n Vergleiche, also O(n)O(n), obwohl ein einzelnes Versickern bis zu ⌊log⁡2n⌋\lfloor \log_2 n \rfloor Ebenen durchläuft.

Beispiel

Heapsort

Mit einem Max-Heap (Elternknoten ≥\ge Kinder, Versickern mit dem größeren Kind) sortiert man ein Array aufsteigend, ohne zusätzlichen Speicher: Erst den Heap aufbauen; dann n−1n - 1 mal die Wurzel (das Maximum) mit dem letzten Eintrag des Heaps tauschen, den Heap um eins verkleinern und die neue Wurzel versickern lassen. Hinter dem Heap wächst so von rechts der sortierte Teil.

ZeileEinrückungAnweisung
10heapsort(A, n):\texttt{heapsort(A, n):}
21aufbauen(A, n)\texttt{aufbauen(A, n)}
31for e = n - 1 down to 1:\texttt{for e = n - 1 down to 1:}
42vertausche(A, 0, e)\texttt{vertausche(A, 0, e)}
52n = e\texttt{n = e}
62versickern(0)\texttt{versickern(0)}

Beispiel [5,2,9,1,7,3][5, 2, 9, 1, 7, 3]: Der Aufbau ergibt den Max-Heap [9,7,5,1,2,3][9, 7, 5, 1, 2, 3].

eeHeap danachsortierter Teil
5[7, 3, 5, 1, 2]9
4[5, 3, 2, 1]7, 9
3[3, 1, 2]5, 7, 9
2[2, 1]3, 5, 7, 9
1[1]2, 3, 5, 7, 9

Laufzeit: Aufbau O(n)O(n), dann n−1n - 1 Versickern zu je O(log⁡n)O(\log n), zusammen O(nlog⁡n)O(n \log n) auch im schlechtesten Fall. Heapsort arbeitet im Array selbst, ist aber nicht stabil: Gleiche Schlüssel können ihre Reihenfolge tauschen.

Heapsort Schritt für Schritt

Heapsort

2 bis 12 ganze Zahlen von 1 bis 99, getrennt durch Komma oder Leerzeichen. Enter übernimmt sie.

Als Baum gelesen (Heap mit 6 Stellen)
529173
Vergleiche
0
Vertauschungen
0
Schreibzugriffe
0
  • V verglichen
  • T getauscht oder geschrieben
  • P Pivot
  • • markiert
  • Arbeitsbereich
  • am Platz
Schritt 1 von 35
Tempo
← → Schritt, Leertaste Abspielen
Die Idee

Das Feld als Baum lesen

Heapsort liest das Feld als Baum: Stelle 0 ist die Wurzel, die Kinder von Stelle i sind die Stellen 2i + 1 und 2i + 2. Zuerst wird daraus ein Max-Heap, ein Baum, in dem jeder Wert mindestens so groß ist wie seine Kinder. Dafür lässt man Werte versickern: Ist ein Wert kleiner als eines seiner Kinder, tauscht er mit dem größeren Kind und wird eine Ebene tiefer weiter geprüft. Steht der Heap, liegt das Maximum an der Wurzel und kann ans Ende getauscht werden.

Pseudocoden = 6, Stellen 0 bis 5
  1. für i von ⌊n / 2⌋ − 1 abwärts bis 0: versickern(i, n)
  2. für ende von n − 1 abwärts bis 1:
  3. tausche A[0] und A[ende]
  4. versickern(0, ende)
  5. versickern(i, größe): solange 2i + 1 < größe:
  6. k ← 2i + 1; wenn k + 1 < größe und A[k + 1] > A[k]: k ← k + 1
  7. wenn A[i] ≥ A[k]: zurück
  8. tausche A[i] und A[k]; i ← k

Laufzeit bei n Zahlen: bester Fall Θ(nlog⁡n)\Theta(n \log n), im Mittel Θ(nlog⁡n)\Theta(n \log n), schlechtester Fall Θ(nlog⁡n)\Theta(n \log n).

Unter den Balken steht der Max-Heap als Baum. Gehe mit Nächster Schritt vorwärts, gib unter Zahlen eine eigene Folge ein und bestätige mit Übernehmen.

Probier es aus

Beispiel

Anwendungen

Kürzeste Wege. Dijkstras Algorithmus (eine spätere Lektion im Kapitel über Graphen) berechnet in einem Straßennetz mit nn Kreuzungen und mm Straßen die kürzesten Wege von einem Startpunkt. Er nimmt immer die noch nicht fertige Kreuzung mit der kleinsten bisher bekannten Entfernung, das ist extrahiereMin\texttt{extrahiereMin}. Findet er einen kürzeren Weg zu einer Kreuzung, fügt er sie mit der neuen Entfernung noch einmal ein und überspringt später den veralteten Eintrag. Mit einem binären Heap sind das O(m)O(m) Heap-Operationen, zusammen O((n+m)log⁡n)O((n + m) \log n).

Ereignissimulation. Simuliert man eine Supermarktkasse, verwaltet man künftige Ereignisse mit ihrem Zeitpunkt als Schlüssel. Man entnimmt immer das früheste, verarbeitet es, und das erzeugt neue Ereignisse. Angenommen, Kunden kommen zu den Zeiten 00, 11 und 55 (Minuten), das Kassieren dauert 33 Minuten, und wartende Kunden stehen in einer gewöhnlichen Warteschlange:

Zeitentnommenes EreignisWirkungEreignisse danach
0Ankunft K1Kasse frei, K1 wird bedientAnkunft K2 (1), Ende K1 (3), Ankunft K3 (5)
1Ankunft K2Kasse belegt, K2 wartetEnde K1 (3), Ankunft K3 (5)
3Ende K1K2 wird bedientAnkunft K3 (5), Ende K2 (6)
5Ankunft K3Kasse belegt, K3 wartetEnde K2 (6)
6Ende K2K3 wird bedientEnde K3 (9)
9Ende K3Kasse freikeine

Die Simulation springt von Ereignis zu Ereignis statt von Minute zu Minute, und die Prioritätswarteschlange liefert die Ereignisse in zeitlicher Reihenfolge, auch wenn sie in anderer Reihenfolge entstehen. Die Standardbibliotheken von Python (heapq\texttt{heapq}) und Java (PriorityQueue\texttt{PriorityQueue}) bieten dafür binäre Min-Heaps an.

Zusammenfassung

  • Eine Prioritätswarteschlange bietet einfuegen, min und extrahiereMin; sie fragt nie nach einem beliebigen Schlüssel.

  • Ein binärer Heap ist ein vollständiger Binärbaum im Array: Kinder von ii bei 2i+12i+1 und 2i+22i+2, Elternknoten bei ⌊(i−1)/2⌋\lfloor (i-1)/2 \rfloor.

  • Min-Heap: Jeder Elternknoten ist höchstens so groß wie seine Kinder. Das Minimum steht in A[0]A[0], sortiert ist das Array nicht.

  • Die Höhe ist ⌊log⁡2n⌋\lfloor \log_2 n \rfloor; Einfügen (Aufsteigen) und extrahiereMin (Versickern mit dem kleineren Kind) kosten O(log⁡n)O(\log n).

  • Aufbau von unten durch Versickern aller inneren Knoten kostet O(n)O(n), weil die Summe der Höhen kleiner als 2n2n ist.

  • Heapsort: Max-Heap aufbauen, dann wiederholt die Wurzel ans Ende tauschen; O(nlog⁡n)O(n \log n), ohne Zusatzspeicher, nicht stabil.

  • Anwendungen: Dijkstras Algorithmus und Ereignissimulation.

Übungen

Aufgabe 1Numerisch

Ein Heap ist ab Index 00 in einem Array gespeichert. Welchen Index hat der Elternknoten des Eintrags mit Index 1010?

Aufgabe 2Multiple Choice

Welches Array ist ein Min-Heap?

Aufgabe 3Numerisch

In den Min-Heap [1,3,2,5,9,8][1, 3, 2, 5, 9, 8] wird der Schlüssel 00 eingefügt. An welchem Index steht danach der Schlüssel 22?

Aufgabe 4Numerisch

Welche Höhe hat ein binärer Heap mit 10001000 Einträgen?

Aufgabe 5Numerisch

Aus dem Array [4,8,3,9,1][4, 8, 3, 9, 1] wird mit aufbauen\texttt{aufbauen} ein Min-Heap gemacht. Welcher Schlüssel steht danach an Index 11?

Aufgabe 6Freitext

Beweise: In einem Min-Heap mit n≥2n \ge 2 Einträgen steht ein größter Schlüssel an einem Index i≥⌊n/2⌋i \ge \lfloor n/2 \rfloor, also in einem Blatt. Wie viele Einträge muss man daher höchstens ansehen, um das Maximum zu finden?

Aufgabe 7Freitext

Gegeben sind nn Zahlen in einem Array. Beschreibe, wie man mit einem Heap die kk kleinsten davon in aufsteigender Reihenfolge in O(n+klog⁡n)O(n + k \log n) Schritten ausgibt, und begründe die Laufzeit. Warum ist das für kleines kk besser als vollständiges Sortieren?