Heaps und Prioritätswarteschlangen
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 Zahlen nur 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, , aber für die Frage nach dem Dringendsten muss man alle Einträge ansehen. Eine sortierte Liste liefert den Dringendsten sofort, aber jedes Einfügen sucht erst die richtige Stelle, im schlechtesten Fall . Ein AVL-Baum schafft beides in , 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.
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?
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:
- : Eintrag hinzufügen.
- : einen Eintrag mit kleinstem Schlüssel zurückgeben, ohne ihn zu entfernen.
- : einen Eintrag mit kleinstem Schlüssel zurückgeben und entfernen.
- : prüfen, ob noch Einträge da sind.
Gleiche Schlüssel sind erlaubt. Viele Umsetzungen bieten zusätzlich , das den Schlüssel eines Eintrags verkleinert, ihn also dringender macht.
Umsetzungen im Vergleich
Umsetzungen im Vergleich
Schlechteste Laufzeiten bei Einträgen:
| Umsetzung | einfuegen | min | extrahiereMin |
|---|---|---|---|
| unsortiertes Array | amortisiert | ||
| sortiertes Array (absteigend) | |||
| AVL-Baum | |||
| binärer Heap |
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 Zahlen in nur aufgebaut werden.
Vollständiger Binärbaum im Array
Ein Binärbaum mit 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 , kann man den Baum in einem Array ablegen. Für den Knoten mit Index gilt dann:
- linkes Kind: , rechtes Kind: , soweit diese Zahl kleiner als ist,
- Elternknoten (für ): .
Dabei ist die größte ganze Zahl . Ein Knoten ist genau dann ein Blatt, wenn , also : Die hintere Hälfte des Arrays besteht aus Blättern.
Warum die Formel stimmt: Ebene hat die Indizes bis . Steht an Stelle seiner Ebene, also , dann stehen vor seinen Kindern in Ebene genau Knoten, und das linke Kind hat den Index .
Heap-Eigenschaft
Ein Array ist ein Min-Heap, wenn für jeden Index gilt:
,
also jeder Elternknoten höchstens so groß wie seine Kinder ist. Beim Max-Heap steht . Wir arbeiten mit Min-Heaps; alles gilt spiegelbildlich für Max-Heaps.
| Index | Schlüssel | Elternindex | linkes Kind | rechtes Kind |
|---|---|---|---|---|
| 0 | 2 | – | 1 | 2 |
| 1 | 4 | 0 | 3 | 4 |
| 2 | 3 | 0 | 5 | 6 |
| 3 | 7 | 1 | 7 | – |
| 4 | 5 | 1 | – | – |
| 5 | 9 | 2 | – | – |
| 6 | 6 | 2 | – | – |
| 7 | 8 | 3 | – | – |
Das ist der Min-Heap . Er ist nicht sortiert: steht vor . Jede Elternzeile ist aber höchstens so groß wie die Kinderzeilen.
Gegenbeispiel: ist kein Min-Heap. Index (Schlüssel ) hat den Elternindex mit Schlüssel .
Minimum an der Wurzel, Höhe logarithmisch
In einem Min-Heap mit Einträgen steht ein kleinster Schlüssel in , und die Höhe des Baums ist .
Minimum: Folgt man von einem Index aus den Elternknoten, erreicht man nach endlich vielen Schritten die , und die Schlüssel werden dabei nach der Heap-Eigenschaft nie größer. Also ist für jedes .
Höhe: Sei die Höhe. Die Ebenen bis sind voll und enthalten Knoten; Ebene enthält mindestens einen und höchstens Knoten. Also , das heißt , und damit .
Welchen Schlüssel hat im Heap der Elternknoten des Index ?
Einfügen: Aufsteigen
Einfügen: Aufsteigen
Der neue Eintrag kommt an die erste freie Stelle ; 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.
| Zeile | Einrückung | Anweisung |
|---|---|---|
| 1 | 0 | |
| 2 | 1 | |
| 3 | 1 | |
| 4 | 1 | |
| 5 | 0 | |
| 6 | 1 | |
| 7 | 2 | |
| 8 | 2 |
Dabei ist . Beispiel: in einfügen.
| Schritt | Vergleich | Array danach | |
|---|---|---|---|
| anhängen | 8 | – | [2, 4, 3, 7, 5, 9, 6, 8, 1] |
| 1 | 8 | , tauschen | [2, 4, 3, 1, 5, 9, 6, 8, 7] |
| 2 | 3 | , tauschen | [2, 1, 3, 4, 5, 9, 6, 8, 7] |
| 3 | 1 | , tauschen | [1, 2, 3, 4, 5, 9, 6, 8, 7] |
| Ende | 0 | Wurzel erreicht | [1, 2, 3, 4, 5, 9, 6, 8, 7] |
Jeder Tausch geht eine Ebene hinauf, also höchstens Tausche: . 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.
Minimum entnehmen: Versickern
Minimum entnehmen: Versickern
Das Minimum steht in . Man ersetzt es durch den letzten Eintrag und verkleinert . Jetzt ist höchstens an der Wurzel etwas verletzt. Der Eintrag versickert: Er wird mit dem kleineren seiner Kinder getauscht, solange dieses kleiner ist.
| Zeile | Einrückung | Anweisung |
|---|---|---|
| 1 | 0 | |
| 2 | 1 | |
| 3 | 1 | |
| 4 | 1 | |
| 5 | 1 | |
| 6 | 1 | |
| 7 | 0 | |
| 8 | 1 | |
| 9 | 2 | |
| 10 | 2 | |
| 11 | 2 | |
| 12 | 2 | |
| 13 | 2 |
Beispiel mit : Entnommen wird , die kommt an die Wurzel.
| Schritt | Kinder | Array danach | |
|---|---|---|---|
| ersetzen | 0 | – | [8, 4, 3, 7, 5, 9, 6] |
| 1 | 0 | , ; kleiner ist , tauschen | [3, 4, 8, 7, 5, 9, 6] |
| 2 | 2 | , ; kleiner ist , tauschen | [3, 4, 6, 7, 5, 9, 8] |
| Ende | 6 | keine Kinder | [3, 4, 6, 7, 5, 9, 8] |
Je Ebene höchstens zwei Vergleiche und ein Tausch, also . Das neue Minimum war ein Kind der alten Wurzel, wie in der Vermutung oben.
Mit dem falschen Kind tauschen
Mit dem falschen Kind tauschen
Beim Versickern wird oft mit dem linken Kind getauscht, oder mit irgendeinem Kind, das kleiner ist. Im Beispiel: Die an der Wurzel hat die Kinder und . Tauscht man mit der , steht an der Wurzel und hat das Kind . Die Heap-Eigenschaft ist verletzt, und liefert statt .
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.
Aus dem Heap wird das Minimum entnommen. Wie sieht das Array danach aus?
Aufbau eines Heaps in
Ein beliebiges Array wird zum Min-Heap, wenn man von hinten nach vorn jeden inneren Knoten versickern lässt (die Blätter ab Index sind schon Heaps aus einem Element):
| Zeile | Einrückung | Anweisung |
|---|---|---|
| 1 | 0 | |
| 2 | 1 | |
| 3 | 2 |
( ist die ganzzahlige Division.) Dieser Aufbau braucht weniger als Vergleiche, also , obwohl ein einzelnes Versickern bis zu Ebenen durchläuft.
Beweisidee: Teuer ist Versickern nur für die wenigen Knoten weit oben; die vielen Knoten unten haben kleine Höhe. Wir summieren die Höhen.
Korrektheit: Wenn beginnt, sind die Teilbäume beider Kinder schon Heaps (sie haben größere Indizes, wurden also schon bearbeitet oder sind Blätter). Versickern macht dann den ganzen Teilbaum von zum Heap. Nach ist das ganze Array ein Heap.
Kosten eines Aufrufs: steigt höchstens so viele Ebenen ab, wie der Knoten hoch ist, mit höchstens zwei Vergleichen je Ebene. Insgesamt sind es also höchstens Vergleiche, wobei die Summe der Höhen aller Knoten ist.
Summe der Höhen: Sei die Höhe des Heaps. Ergänzt man die unterste Ebene zu einem vollen Baum der Höhe , wird kein Knoten niedriger. In diesem vollen Baum haben genau Knoten die Höhe . Also
Heapsort
Heapsort
Mit einem Max-Heap (Elternknoten Kinder, Versickern mit dem größeren Kind) sortiert man ein Array aufsteigend, ohne zusätzlichen Speicher: Erst den Heap aufbauen; dann 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.
| Zeile | Einrückung | Anweisung |
|---|---|---|
| 1 | 0 | |
| 2 | 1 | |
| 3 | 1 | |
| 4 | 2 | |
| 5 | 2 | |
| 6 | 2 |
Beispiel : Der Aufbau ergibt den Max-Heap .
| Heap danach | sortierter 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 , dann Versickern zu je , zusammen auch im schlechtesten Fall. Heapsort arbeitet im Array selbst, ist aber nicht stabil: Gleiche Schlüssel können ihre Reihenfolge tauschen.
Heapsort
- Vergleiche
- 0
- Vertauschungen
- 0
- Schreibzugriffe
- 0
- V verglichen
- T getauscht oder geschrieben
- P Pivot
- • markiert
- Arbeitsbereich
- am Platz
Das Feld als Baum lesen
für i von ⌊n / 2⌋ − 1 abwärts bis 0: versickern(i, n)für ende von n − 1 abwärts bis 1:tausche A[0] und A[ende]versickern(0, ende)versickern(i, größe): solange 2i + 1 < größe:k ← 2i + 1; wenn k + 1 < größe und A[k + 1] > A[k]: k ← k + 1wenn A[i] ≥ A[k]: zurücktausche A[i] und A[k]; i ← k
Laufzeit bei n Zahlen: bester Fall , im Mittel , schlechtester Fall .
Probier es aus
Anwendungen
Anwendungen
Kürzeste Wege. Dijkstras Algorithmus (eine spätere Lektion im Kapitel über Graphen) berechnet in einem Straßennetz mit Kreuzungen und 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 . 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 Heap-Operationen, zusammen .
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 , und (Minuten), das Kassieren dauert Minuten, und wartende Kunden stehen in einer gewöhnlichen Warteschlange:
| Zeit | entnommenes Ereignis | Wirkung | Ereignisse danach |
|---|---|---|---|
| 0 | Ankunft K1 | Kasse frei, K1 wird bedient | Ankunft K2 (1), Ende K1 (3), Ankunft K3 (5) |
| 1 | Ankunft K2 | Kasse belegt, K2 wartet | Ende K1 (3), Ankunft K3 (5) |
| 3 | Ende K1 | K2 wird bedient | Ankunft K3 (5), Ende K2 (6) |
| 5 | Ankunft K3 | Kasse belegt, K3 wartet | Ende K2 (6) |
| 6 | Ende K2 | K3 wird bedient | Ende K3 (9) |
| 9 | Ende K3 | Kasse frei | keine |
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 () und Java () 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 bei und , Elternknoten bei .
Min-Heap: Jeder Elternknoten ist höchstens so groß wie seine Kinder. Das Minimum steht in , sortiert ist das Array nicht.
Die Höhe ist ; Einfügen (Aufsteigen) und extrahiereMin (Versickern mit dem kleineren Kind) kosten .
Aufbau von unten durch Versickern aller inneren Knoten kostet , weil die Summe der Höhen kleiner als ist.
Heapsort: Max-Heap aufbauen, dann wiederholt die Wurzel ans Ende tauschen; , ohne Zusatzspeicher, nicht stabil.
Anwendungen: Dijkstras Algorithmus und Ereignissimulation.
Übungen
Ein Heap ist ab Index in einem Array gespeichert. Welchen Index hat der Elternknoten des Eintrags mit Index ?
Welches Array ist ein Min-Heap?
In den Min-Heap wird der Schlüssel eingefügt. An welchem Index steht danach der Schlüssel ?
Welche Höhe hat ein binärer Heap mit Einträgen?
Aus dem Array wird mit ein Min-Heap gemacht. Welcher Schlüssel steht danach an Index ?
Beweise: In einem Min-Heap mit Einträgen steht ein größter Schlüssel an einem Index , also in einem Blatt. Wie viele Einträge muss man daher höchstens ansehen, um das Maximum zu finden?
Gegeben sind Zahlen in einem Array. Beschreibe, wie man mit einem Heap die kleinsten davon in aufsteigender Reihenfolge in Schritten ausgibt, und begründe die Laufzeit. Warum ist das für kleines besser als vollständiges Sortieren?