Heap und Priority Queue

1. Die Priority Queue

Eine Priority Queue kann zwei Dinge:

• push legt einen Eintrag mit einer Priorität hinein,
• pop nimmt den Eintrag mit der kleinsten Priorität heraus und gibt ihn zurück.

Wie sie das macht, ist erst einmal egal. Die einfachste Art, eine Liste, in der pop jedes Mal den kleinsten sucht, ist richtig, aber pop muss dafür alle Einträge ansehen. Eine sortierte Liste macht pop schnell, dafür muss push die richtige Stelle finden und alles dahinter verschieben. Ein Heap macht beides schnell:

Priority Queues stecken in Dijkstra und A* (Graphen und Wege), in Huffman-Codes (die zwei seltensten Bäume zuerst), in jedem Terminkalender und in jedem Betriebssystem, das entscheidet, welches Programm als Nächstes rechnen darf.

2. Der binäre Heap

Ein Array als Baum

Ein binärer Heap ist ein Array, das man sich als Baum denkt. Ganz oben steht der Eintrag an Index 0. Die Kinder des Eintrags an Index \(i\) stehen an den Indizes \(2i + 1\) und \(2i + 2\), sein Elternteil an \(\lfloor (i - 1) / 2 \rfloor\):

Der Baum ist immer von oben nach unten und in jeder Zeile von links nach rechts gefüllt, ohne Lücken. Deshalb braucht er keine Zeiger: Das Array ist der Baum.

Die Heap-Eigenschaft

Für jeden Eintrag gilt: Kein Kind ist kleiner als sein Elternteil. Daraus folgt, dass ganz oben, an Index 0, der kleinste Eintrag steht. Geschwister sind dabei nicht geordnet, und eine Zeile weiter unten kann kleinere Zahlen haben als eine weiter oben, nur eben nicht unter demselben Elternteil. Ein Heap ist also nicht sortiert, er ist gerade so geordnet, dass man den kleinsten Eintrag sofort findet.

3. push

Ein neuer Eintrag kommt hinten an das Array, an die erste freie Stelle des Baums. Dort verletzt er vielleicht die Heap-Eigenschaft: Er ist kleiner als sein Elternteil. Dann tauscht er mit ihm den Platz, und das so lange, bis sein Elternteil nicht mehr größer ist oder er oben angekommen ist. Er sickert nach oben.

push(heap, eintrag):
    eintrag hinten an heap anfügen
    i ← letzter Index von heap
    solange i > 0:
        eltern ← (i - 1) / 2, abgerundet
        wenn heap[eltern] ≤ heap[i]: fertig
        heap[eltern] und heap[i] tauschen
        i ← eltern

Probier es aus mit 5, 3, 8, 1, 4 und 2. Oben steht der Heap als Baum, darunter dasselbe als Array, mit den Indizes klein daneben:

Ein Eintrag steigt höchstens so viele Stufen auf, wie der Baum hoch ist: bei \(n\) Einträgen etwa \(\log_2 n\), bei einer Million also 20.

4. pop

Der kleinste Eintrag steht an Index 0. Ihn herauszunehmen, reißt ein Loch an der Spitze. Also kommt der letzte Eintrag des Arrays dorthin, und das Array wird um eins kürzer. Der neue an der Spitze ist meist zu groß. Er tauscht mit dem kleineren seiner beiden Kinder, solange dieses kleiner ist als er. Er sickert nach unten.

pop(heap):
    wenn heap leer: es gibt nichts
    oben ← heap[0]
    letzter ← den letzten Eintrag aus heap nehmen
    wenn heap nicht leer:
        heap[0] ← letzter
        i ← 0
        wiederholen:
            kleinster ← i
            für kind in (2i + 1, 2i + 2):
                wenn kind < Länge von heap und heap[kind] < heap[kleinster]:
                    kleinster ← kind
            wenn kleinster = i: fertig
            heap[kleinster] und heap[i] tauschen
            i ← kleinster
    gib oben zurück

Erst kommen 5, 3, 8, 1, 4 und 2 hinein, dann holt pop dreimal den kleinsten heraus:

Typische Fehler

• Mit dem größeren Kind tauschen oder mit dem ersten, das kleiner ist. Dann steht das kleinere Geschwister über dem größeren, und die Heap-Eigenschaft ist kaputt.
• Den letzten Eintrag erst entfernen, nachdem man ihn an Index 0 geschrieben hat. Bei einem Heap mit nur einem Eintrag bleibt er dann stehen.
• Prüfen, ob ein Kind existiert, ohne die Länge des Arrays: 2i + 1 kann hinter dem Ende liegen.
• Prioritäten und Werte trennen: Liegen Paare aus Priorität und Wert im Heap, wird nur die Priorität verglichen, sonst entscheidet bei gleicher Priorität der Wert, und der lässt sich vielleicht gar nicht vergleichen.

5. Sortieren mit einem Heap

Legt man alle Zahlen mit push in einen Heap und holt sie mit pop wieder heraus, kommen sie sortiert heraus, die kleinste zuerst. Das ist Heapsort. Es braucht für \(n\) Zahlen \(n\)-mal push und \(n\)-mal pop, jedes höchstens \(\log_2 n\) Schritte: zusammen \(O(n \log n)\), so schnell wie die besten Sortierverfahren, auch im schlechtesten Fall.

Ohne zweites Array geht es auch: Man baut den Heap im Array selbst auf und legt den jeweils größten Eintrag (mit einem Heap, in dem kein Kind größer ist als sein Elternteil) ans Ende, in den Teil, der schon sortiert ist. In der Sorting Sandbox kannst du Heapsort selbst programmieren und mit den anderen Verfahren vergleichen.