Ein Heap ist eine Datenstruktur, die auf einer besonderen Baum-Form basiert und immer das kleinste oder größte Element schnell liefert. Man unterscheidet den Min-Heap (Elternknoten kleiner oder gleich seinen Kindern — das Minimum steht oben) und den Max-Heap (Elternknoten größer oder gleich — das Maximum steht oben).
Aufbau und Eigenschaften
Ein Binär-Heap ist ein fast vollständiger Binärbaum: Alle Ebenen sind bis auf die letzte voll besetzt, und die letzte Ebene ist linksbündig gefüllt. Dadurch lässt sich der Heap erstaunlich kompakt in einem Array ablegen: Die Wurzel steht an Position 0, die Kinder eines Knotens an Position i stehen an 2i+1 und 2i+2, der Elternknoten von Position i an (i-1)/2. Man braucht keine Pointer — nur Indexrechnung.
Operationen
- Einfügen (insert): Das neue Element wird ans Ende gesetzt und nach oben getauscht, bis die Heap-Eigenschaft stimmt — O(log n).
- Minimum/Maximum abfragen (peek): Das oberste Element — O(1).
- Entfernen (extract-min/extract-max): Das Wurzelelement wird entfernt, das letzte Element rückt nach und wird nach unten getauscht (heapify) — O(log n).
Wozu ein Heap dient
Heaps sind die klassische Implementierung einer Prioritätswarteschlange: Elemente mit hoher Priorität kommen immer zuerst, auch wenn sie später eingefügt wurden. So arbeiten zum Beispiel Dijkstras kürzeste-Wege-Algorithmus und die Heapsort-Sortierung in O(n log n). Im Gegensatz zur normalen Queue (FIFO) oder zum Stack (LIFO) bestimmt hier der Wert die Reihenfolge. Auch ein Datenbank- oder Betriebssystem-Scheduler nutzt Heaps, um den nächsten Prozess auszuwählen. Zusammen mit Hash-Tabellen, verketteten Listen und dem passenden Datentyp gehört der Heap zum Grundwerkzeug der Algorithmen-Technik.