Heap und Prioritätswarteschlange

Kurz: Ein Heap ist ein Baum, bei dem jeder Knoten kleiner (Min-Heap) oder größer (Max-Heap) ist als seine Kinder. Damit liegt das kleinste bzw. größte Element immer ganz oben.

Genauer: Eine Prioritätswarteschlange gibt immer das Element mit der höchsten Priorität zuerst heraus. Mit einem Heap dauern Einfügen und Entnehmen nur O(log n). Das Auslesen des Minimums kostet O(1).

Im Detail

• Speicherung: Als Array: Kinder von Index i liegen bei 2i+1 und 2i+2.
• Einfügen: Ans Ende setzen und nach oben „aufsteigen” lassen („sift up”).
• Entnehmen: Wurzel nehmen, letztes Element an die Wurzel setzen, nach unten sinken lassen.
• Anwendung: Dijkstra-Algorithmus, Aufgabenplanung (Scheduler), Ereignissimulation, Heapsort, „die k größten Elemente”.
• Heapsort: Baut einen Heap und entnimmt nacheinander: O(n log n), in-place.
• Nicht zu verwechseln: Der Heap-Speicher (Stack und Heap) ist etwas anderes.

Siehe auch: Baum-Datenstruktur, Queue-Datenstruktur