Was ist ein Stapel?

Ein Heap ist eine spezielle baumartige Datenstruktur, die die Heap-Eigenschaft erfüllt. Diese Eigenschaft besagt, dass für jeden Knoten, außer der Wurzel, der Wert des Schlüssels dieses Knotens in einem bestimmten Verhältnis zum Wert des Schlüssels seines Elternteils stehen muss. Es gibt zwei Haupttypen von Heaps:

• Max-Heap: Der Wert des Schlüssels jedes Knotens ist nicht kleiner als der Wert der Schlüssel seiner Kinder. Das maximale Element befindet sich an der Wurzel.
• Min-Heap: Der Wert des Schlüssels jedes Knotens ist nicht größer als der Wert der Schlüssel seiner Kinder. Das minimale Element befindet sich an der Wurzel.

Der Heap wird in der Regel als Array implementiert, was einen effizienten Zugriff auf die Elemente und die Durchführung von Operationen ermöglicht. Die Beziehung zwischen Eltern und Kindern im Array ist wie folgt:

• Für ein Element mit Index i (beginnend bei 0) befindet sich sein linker Nachfolger bei Index 2i + 1.
• Sein rechter Nachfolger befindet sich bei Index 2i + 2.
• Sein Elternteil befindet sich bei Index floor((i - 1) / 2).

Hauptoperationen am Heap:

• Einfügen: Hinzufügen eines neuen Elements. Laufzeit O(log n), wobei n die Anzahl der Elemente ist.
• Extract-Max / Extract-Min: Entfernen und Zurückgeben des maximalen (bei Max-Heap) oder minimalen (bei Min-Heap) Elements. Laufzeit O(log n).
• Heapify (Heap-Bildung): Umwandlung eines beliebigen Arrays in einen Heap. Laufzeit O(n).

Heaps werden in Sortieralgorithmen (z.B. Heapsort), in Prioritätswarteschlangen und in Algorithmen zur kürzesten Pfadsuche (z.B. Dijkstra-Algorithmus) verwendet.