heapq in Python: Prioritätswarteschlangen und Heaps effizient nutzen

Es gibt eine Klasse von Problemen, die immer wieder auftaucht: Du hast eine Menge von Elementen und brauchst wiederholt das kleinste (oder größte) davon – aber die Menge verändert sich ständig, weil laufend neue Elemente dazukommen. Die naheliegende Lösung, die Liste jedes Mal neu zu sortieren, ist verlockend einfach und leider erstaunlich langsam. Für genau dieses Muster hat die Python-Standardbibliothek das Modul heapq im Gepäck.

Was ein Heap überhaupt ist

Ein Heap ist ein binärer Baum mit einer einzigen Regel: Jeder Elternknoten ist kleiner oder gleich seinen Kindern. Das bedeutet, dass das kleinste Element immer an der Wurzel sitzt – und damit in konstanter Zeit ablesbar ist. In Python wird dieser Baum platzsparend als ganz normale Liste gespeichert; du musst dir die Baumstruktur also gar nicht selbst vorstellen. Das heapq-Modul verwaltet eine solche Liste als sogenannten Min-Heap und garantiert, dass heap[0] stets das kleinste Element ist.

Die wichtigsten Funktionen

Anstatt einer eigenen Klasse arbeitet heapq direkt auf einer Liste. Die beiden Arbeitspferde sind heappush und heappop:

import heapq

heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)

print(heap[0])          # 1 – das kleinste Element, ohne es zu entfernen
print(heapq.heappop(heap))  # 1 – kleinstes Element entnehmen
print(heapq.heappop(heap))  # 3

Sowohl das Einfügen als auch das Entnehmen laufen in logarithmischer Zeit, also O(log n). Genau das ist der entscheidende Vorteil gegenüber der immer neu sortierten Liste, bei der jede Einfügung O(n log n) kostet. Wenn du bereits eine fertige Liste hast, verwandelt heapq.heapify(liste) sie in linearer Zeit direkt an Ort und Stelle in einen gültigen Heap.

Praktische Helfer: nlargest und nsmallest

Häufig willst du gar nicht den kompletten Heap verwalten, sondern nur die drei größten oder die fünf kleinsten Werte aus einer Sammlung. Dafür gibt es heapq.nlargest und heapq.nsmallest, die beide auch einen key-Parameter akzeptieren – genau wie sorted:

aufgaben = [("Backup", 2), ("Deploy", 9), ("Report", 5)]
top = heapq.nlargest(2, aufgaben, key=lambda t: t[1])
# [("Deploy", 9), ("Report", 5)]

Prioritätswarteschlangen richtig bauen

Der klassische Einsatzzweck ist die Prioritätswarteschlange. Der übliche Trick: Du legst Tupel der Form (priorität, zähler, objekt) in den Heap. Die Priorität sorgt für die Reihenfolge, und ein mitlaufender Zähler verhindert, dass Python bei gleicher Priorität versucht, die eigentlichen Objekte zu vergleichen – was bei nicht vergleichbaren Objekten sonst zu einem Fehler führt. Dieser kleine Kunstgriff ist der Unterschied zwischen einer sauber laufenden Warteschlange und einem schwer zu findenden Bug.

Wo es sich lohnt, tiefer einzusteigen

Wer die englische Perspektive und noch mehr Beispiele – etwa zum Zusammenführen mehrerer sortierter Ströme mit heapq.merge – sehen möchte, dem sei der ausführliche Deep Dive unserer Schwesterseite pykit.org ans Herz gelegt: Always-Sorted, Never Slow: A Practical Deep Dive into Python's heapq. Der Artikel geht besonders schön auf die Laufzeiteigenschaften und typische Fallstricke ein und ergänzt die hier gezeigten Grundlagen ideal.

Fazit

Immer wenn du in einer Schleife das Kleinste oder Größte aus einer wachsenden Menge brauchst, ist heapq fast immer die richtige Antwort. Es ist Teil der Standardbibliothek, braucht keinerlei Installation und ersetzt viele Zeilen fehleranfälligen Sortier-Codes durch drei, vier klare Funktionsaufrufe. Merke dir die Faustregel: Sortierte Liste bei statischen Daten, Heap bei ständigem Nachschub.