Welche Klassifikationen von Heaps gibt es im Kontext von Datenstrukturen?

Im Kontext der Datenstrukturen wird unter "Heap" (Heap) meist ein binärer Heap (Binary Heap) verstanden, der folgende Klassifikationen aufweist:

1. Nach Art der Ordnung:

   • Min-Heap (Min-Heap): Der Wert jedes Knotens ist kleiner oder gleich den Werten seiner Kindknoten. Die Wurzel ist das minimale Element.
   • Max-Heap (Max-Heap): Der Wert jedes Knotens ist größer oder gleich den Werten seiner Kindknoten. Die Wurzel ist das maximale Element.

2. Nach Vollständigkeit des Baumes:

   • Vollständiger binärer Heap (Complete Binary Heap): Alle Ebenen, außer möglicherweise die letzte, sind vollständig gefüllt, und die Knoten auf der letzten Ebene sind so weit wie möglich nach links verschoben. Diese Eigenschaft ist wichtig, da sie eine effiziente Speicherung des Heaps in einem Array ermöglicht.

   // Beispielstruktur für einen Heap-Knoten (zur Demonstration des Konzepts)
   public class HeapNode<T>
   {
       public T Value { get; set; }
       // Verweise auf Kindknoten sind in der arraybasierten Darstellung nicht immer explizit
       public HeapNode<T> Left { get; set; }
       public HeapNode<T> Right { get; set; }
   }
   

Obwohl es auch andere Arten von Heaps gibt, wie Fibonacci-Heaps (für fortgeschrittene Algorithmen) oder Binomial-Heaps, bezieht man sich in den meisten Fällen bei "Heap" auf einen vollständigen binären Min- oder Max-Heap, aufgrund ihrer breiten Anwendung in Sortieralgorithmen (z.B. Heapsort) und Prioritätswarteschlangen.