Was ist ein Heap?
Ein Heap (auf Deutsch Halde) ist eine Datenstruktur, die den kleinsten Wert immer ganz oben bereithält. Er ist die Grundlage der Prioritätswarteschlange, mit der ein Rechner das Dringendste zuerst erledigt.
Ein Rechner der Hochschule bekommt Aufträge mit einer Priorität. Der Auftrag mit der kleinsten Zahl ist am dringendsten und läuft zuerst.
Am Ende dieser Lektion
Notiz
Ich kann mit einem Heap den kleinsten Wert bereithalten.
Schlüsselwörter
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Heap | ein Baum, in dem jeder Knoten höchstens so groß ist wie seine Kinder | |
| Priorität | eine Zahl, die sagt, wie dringend etwas ist | 1 |
| Prioritätswarteschlange | eine Warteschlange, die das Dringendste zuerst herausgibt | |
| Aufsteigen | einen Wert nach oben tauschen, bis die Regel stimmt | |
| Versickern | einen Wert nach unten tauschen, bis die Regel stimmt |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Im Heap steht das Kleinste oben
Ein Heap ist ein Baum, bei dem jeder Knoten höchstens so groß ist wie seine Kinder. Damit steht das Kleinste immer an der Spitze. Die Kinder untereinander sind nicht sortiert. Gespeichert wird er in einer einfachen Liste. Die Tabelle zeigt, welche Plätze die Kinder eines Platzes haben.
Die Plätze von Eltern und Kindern
| Platz | Erstes Kind | Zweites Kind |
|---|---|---|
| 0 | 1 | 2 |
| 1 | 3 | 4 |
| 2 | 5 | 6 |
| 3 | 7 | 8 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Einen Heap mit heapq bauen
Das Modul heapq gehört zu Python. heapify macht aus einer Liste einen Heap. heappop nimmt die Spitze heraus. Der erste Befehl gibt die Spitze aus. Der zweite nimmt dreimal nacheinander die Spitze heraus.
Die Spitze eines Heaps ausgeben
python3 -c "import heapq; h = [9, 5, 8, 2, 6, 3]; heapq.heapify(h); print(h[0])"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Dreimal die Spitze herausnehmen
python3 -c "import heapq; h = [9, 5, 8, 2, 6, 3]; heapq.heapify(h); print(heapq.heappop(h), heapq.heappop(h), heapq.heappop(h))"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Push hängt hinten an und lässt aufsteigen
Beim push hängen Sie den Wert hinten an. Dann tauschen Sie ihn mit seinem Elternplatz, solange er kleiner ist. Das ist das Aufsteigen. Beim pop nehmen Sie die Spitze heraus. Der letzte Wert kommt nach oben und sickert nach unten: Sie tauschen ihn mit dem kleineren Kind, solange er größer ist. Beide Wege sind höchstens so lang wie die Höhe des Baums.
Beispiel: die 1 einfügen
| Schritt | Liste | Was passiert |
|---|---|---|
| Anhängen | 2 5 3 9 6 8 1 | Die 1 steht auf Platz 6 |
| 1 | 2 5 1 9 6 8 3 | Eltern ist Platz 2 (3), die 1 ist kleiner: Tausch |
| 2 | 1 5 2 9 6 8 3 | Eltern ist Platz 0 (2), die 1 ist kleiner: Tausch |
| Ende | 1 5 2 9 6 8 3 | Platz 0 hat keine Eltern: fertig |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Einen Wert aufsteigen lassen
# Eine 1 in einen Heap einfuegen und aufsteigen lassen.
halde = [2, 5, 3, 9, 6, 8]
halde.append(1)
platz = len(halde) - 1
while platz > 0 and halde[platz] < halde[(platz - 1) // 2]:
eltern = (platz - 1) // 2
merk = halde[platz]
halde[platz] = halde[eltern]
halde[eltern] = merk
platz = eltern
print(halde)
# Fuegen Sie statt der 1 die 7 ein: sie bleibt ganz hinten.
Beispiel: die Spitze herausnehmen
| Schritt | Liste | Was passiert |
|---|---|---|
| Start | 1 5 2 9 6 8 3 | Die 1 ist die Spitze |
| Letzten nach oben | 3 5 2 9 6 8 | Die 3 steht an der Spitze |
| Tausch | 2 5 3 9 6 8 | Kinder 5 und 2: die 2 ist kleiner |
| Ende | 2 5 3 9 6 8 | Das Kind der 3 ist die 8, also fertig |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Eine Prioritätswarteschlange liefert das Dringendste
Ein Heap von Aufträgen ergibt eine Prioritätswarteschlange. Jeder Auftrag ist ein Paar aus Priorität und Name. Die kleinste Priorität ist die dringendste. Mit push kommt ein Auftrag hinzu, mit pop kommt der dringendste heraus. Bei gleicher Priorität entscheidet der Name nach dem Alphabet.
Aufträge nach Priorität herausnehmen
# Eine Prioritaetswarteschlange mit dem Modul heapq.
import heapq
auftraege = []
heapq.heappush(auftraege, [3, "Backup"])
heapq.heappush(auftraege, [1, "Sicherheitsupdate"])
heapq.heappush(auftraege, [2, "Mail-Versand"])
while len(auftraege) > 0:
print(heapq.heappop(auftraege))
# Fuegen Sie [1, "Abrechnung"] hinzu: wer kommt zuerst?
Ein häufiger Fehler
Warnung
Viele denken, ein Heap sei sortiert, wenn man die Liste von vorn liest. Die Liste 1 5 2 9 6 8 3 ist ein gültiger Heap, aber nicht sortiert. Nur die Spitze ist sicher die kleinste. Für eine sortierte Ausgabe nehmen Sie so oft pop, bis der Heap leer ist.