What is a Heap?

Ein Heap ist eine baumförmige Datenstruktur, die einer einfachen Invariante folgt: Jeder Elternknoten ist kleiner als (oder gleich groß wie) seine Kinder. Der kleinste Wert befindet sich immer an der Wurzel und kann in O(1) gelesen werden. Diese spezielle Variante wird als Min-Heap bezeichnet; das Spiegelbild mit einer "Größter-an-der-Wurzel"-Invariante ist ein Max-Heap.

Der clevere Teil ist die Speicherung. Obwohl wir ihn uns als Baum vorstellen, lebt ein Heap in einem flachen Array. Für den Knoten am Index i:

• Sein Elternknoten befindet sich am Index (i - 1) / 2.
• Sein linkes Kind befindet sich am Index 2 * i + 1.
• Sein rechtes Kind befindet sich am Index 2 * i + 2.

Keine Pointer, keine Knotenobjekte: nur Index-Mathematik. Das macht Heaps sehr Cache-freundlich und einfach zu implementieren.

Die fünf Hauptoperationen eines Min-Heaps sind:

1. Peek: Gibt den kleinsten Wert (die Wurzel) zurück.
2. Insert: Fügt einen Wert hinzu und lässt ihn an seine Position aufsteigen ("bubble up").
3. ExtractMin: Entfernt den kleinsten Wert und gibt ihn zurück.
4. Size: Gibt zurück, wie viele Werte gespeichert sind.
5. IsEmpty: Prüft, ob der Heap leer ist.

Erstellen wir eine MinHeap-Klasse!