Was ist ein Stapel (im Kontext von Datenstrukturen)?

Ein Heap ist ein spezieller Baum, der als Datenstruktur verwendet wird. Die Haupteigenschaft eines Heaps ist die partielle Ordnung: Für jeden Knoten gilt die Bedingung, dass der Wert des Elternknotens größer oder gleich dem Wert eines jeden seiner Kindknoten (Max-Heap) oder kleiner oder gleich (Min-Heap) ist.

Wichtige Merkmale:

• Binärbaum: Wird meist als binärer Baum implementiert, bei dem jeder Knoten höchstens zwei Nachkommen hat.
• Vollständiger binärer Baum: Auf allen Ebenen, außer möglicherweise der letzten, ist der Baum vollständig gefüllt. Die Knoten auf der letzten Ebene werden von links nach rechts gefüllt. Dies ermöglicht eine effiziente Speicherung des Heaps in einem Array.
• Heap-Eigenschaft:
  • Max-Heap: Der Wert jedes Knotens ist größer oder gleich den Werten seiner Kindknoten. Das maximale Element befindet sich immer an der Wurzel.
  • Min-Heap: Der Wert jedes Knotens ist kleiner oder gleich den Werten seiner Kindknoten. Das minimale Element befindet sich immer an der Wurzel.

Hauptoperationen mit dem Heap:

• Element einfügen: Hinzufügen eines neuen Elements und Erhaltung der Heap-Eigenschaft.
• Element entfernen: Entfernen des Wurzel-Elements (maximal oder minimal, je nach Heap-Typ) und Erhaltung der Heap-Eigenschaft.
• Heap erstellen: Aufbau eines Heaps aus einem Array von Elementen.

Anwendungen des Heaps:

• Sortierung: Heapsort-Algorithmus.
• Prioritätswarteschlangen: Effiziente Implementierung von Warteschlangen, bei denen Elemente nach Priorität verarbeitet werden.
• Suchalgorithmen: Zum Beispiel die Suche nach dem k-ten Element nach Wert.
• Graphenalgorithmen: Zum Beispiel Dijkstra-Algorithmus.

Darstellung des Heaps in einem Array:

Da der Heap ein vollständiger binärer Baum ist, kann er effizient in einem Array ohne Zeiger gespeichert werden.

• Wenn ein Knoten den Index i hat, befindet sich sein linker Nachkomme bei Index 2*i + 1.
• Sein rechter Nachkomme befindet sich bei Index 2*i + 2.
• Sein Elternteil befindet sich bei Index (i - 1) / 2.

# Beispiel für die Darstellung eines Min-Heaps als Array
heap_array = [10, 15, 20, 17, 25, 30]

# Wurzel: heap_array[0] = 10
# Linker Nachkomme der Wurzel: heap_array[2*0 + 1] = heap_array[1] = 15
# Rechter Nachkomme der Wurzel: heap_array[2*0 + 2] = heap_array[2] = 20
# Elternteil des Elements bei Index 3 (17): heap_array[(3-1)//2] = heap_array[1] = 15