Heap-Datenstruktur

Eine Heap-Datenstruktur ist eine spezialisierte baumbasierte Datenstruktur, die die Heap-Eigenschaft erfüllt: entweder das Element mit der höchsten Priorität (max heap) oder das Element mit der niedrigsten Priorität (min heap) wird immer an der Wurzel gespeichert. Dies ermöglicht einen effizienten Zugriff auf das Element mit der höchsten oder niedrigsten Priorität. Neben Heap-Datenstrukturen gibt es auch noch den für die Programmierung wichtigen Heap im Kontext der Speicherverwaltung.

Inhaltsverzeichnis

Max-Heap

In einem Max Heap ist der übergeordnete Knoten immer größer oder gleich seinen Kindern. In einem Min-Heap ist das übergeordnete Element immer kleiner oder gleich seinen Kindern. Die Elemente werden in einem Array gespeichert, so dass die Kinder des Elements mit dem Index i unter den Indizes 2i+1 und 2i+2 gespeichert werden.

Heap Datenstruktur – Diese Art von Heap-Datenstruktur wird auch als binärer Heap bezeichnet.

Heaps werden häufig für die Implementierung von Prioritätswarteschlangen und für Sortieralgorithmen wie Heap Sort verwendet. Sie haben eine effiziente O(log n)-Zeitkomplexität für Einfügungen und Löschungen und eine O(1)-Zeitkomplexität für die Suche nach dem maximalen oder minimalen Element, was sie für den Einsatz in Echtzeitanwendungen geeignet macht.

Heap-Diagramm, das einen binaeren Heap zeigt, mit einem Max-Heap und einem Min-Heap nebeneinander

Anwendungsbeispiele von Heaps

Heaps sind nicht nur ein interessantes theoretisches Konzept, sondern sie haben auch eine Vielzahl praktischer Anwendungen in realen Szenarien. Einige prominente Anwendungen von Heaps sind:

Netzwerk-Scheduling: In Computernetzwerken, insbesondere in Hochgeschwindigkeitsnetzwerken, ist es von entscheidender Bedeutung, Pakete mit unterschiedlichen Prioritäten effizient zu verarbeiten. Heaps, insbesondere Min-Heaps, sind nützlich, um den Paketfluss zu priorisieren und sicherzustellen, dass hochpriorisierte Pakete bevorzugt behandelt werden.
Datenstrommanagement: Bei der Verarbeitung von Datenströmen, bei denen ständig Daten ankommen und verarbeitet werden müssen, können Heaps verwendet werden, um Statistiken wie den Median oder den k-ten kleinsten Wert in Echtzeit zu berechnen.
Optimierungsprobleme: Viele Optimierungsprobleme, wie z. B. das Problem des kürzesten Pfads in einem gewichteten Graphen, können effizient mit Heaps gelöst werden. Heaps sind nützlich, um den Knoten mit dem geringsten Gewicht schnell zu identifizieren und zu entfernen.

Heapify

Heapify ist der Prozess der Erstellung einer Heap-Datenstruktur aus einem Binärbaum. Er wird verwendet, um einen Min-Heap oder einen Max-Heap zu erstellen.

Heap Algorithmus

Im Folgenden werden einige der wichtigsten Operationen auf einem Heap zusammen mit ihren Algorithmen beschrieben.

Heapify Code-Beispiel in JavaScript

function heapify(array, size, i) {
let largest = i;
let leftChild = 2 * i + 1;
let rightChild = 2 * i + 2;

if (leftChild < size && array[leftChild] > array[largest]) 
  {
   largest = leftChild;
  }
if (rightChild < size && array[rightChild] > array[largest])

  {
  largest = rightChild;
  }

if (largest !== i)

   [array[i], array[largest]] = [array[largest], array[i]];
    heapify(array, size, largest);
   }
}

Binärer Heap

Ein binärer Heap ist eine baumbasierte Datenstruktur, die die halbgeordneten Baum-Eigenschaften erfüllt.
Das bedeutet, dass jeder Knoten eine bestimmte Beziehung zu seinen Kindern, aber nicht notwendigerweise zu seinen Geschwistern, hat.

Zwei Haupttypen von binären Heaps

Es gibt zwei Haupttypen von binären Heaps:

Max-Heaps und Min-Heaps. In einem Max-Heap ist der Wert eines jeden Knotens immer größer oder gleich den Werten seiner Kinder, während in einem Min-Heap der Wert eines jeden Knotens immer kleiner oder gleich den Werten seiner Kinder ist.

Binäre Heaps haben viele Anwendungen in der Informatik, insbesondere in Algorithmen, die Prioritäts-Warteschlangen verwenden, wie Dijkstra’s Algorithmus für kürzeste Pfade. Eine der Hauptstärken von binären Heaps ist ihre Fähigkeit, sowohl Einfüge- als auch Entfernungsoperationen in logarithmischer Zeit auszuführen, was sie zu einer effizienten Datenstruktur für viele Anwendungen macht.

Entscheidungsbaum Heapsort

Heapsort ist ein effizienter Vergleichsbasiert-Sortieralgorithmus, der die Struktur eines binären Heaps nutzt.
Der grundlegende Gedanke hinter Heapsort ist einfach:

Baue zuerst einen Max-Heap aus den Eingabedaten auf. Da der größte Wert an der Wurzel des Max-Heaps steht, kann dieser Wert entfernt und am Ende des sortierten Arrays platziert werden. Danach wird die Heap-Eigenschaft wiederhergestellt, und der nächstgrößte Wert kann erneut entfernt und platziert werden.

Dieser Prozess wird wiederholt, bis der gesamte Heap sortiert ist. Interessanterweise findet der gesamte Sortierprozess im ursprünglichen Array statt, wodurch kein zusätzlicher Speicher benötigt wird.

Während der Name „Entscheidungsbaum“ oft in Bezug auf Sortieralgorithmen verwendet wird, um die verschiedenen Vergleichsentscheidungen darzustellen, die beim Sortieren getroffen werden, ist Heapsort einzigartig darin, dass er die Baumstruktur eines Heaps direkt nutzt, um die Sortierung durchzuführen.

Vergleich der Heap-Datenstruktur mit anderen Datenstrukturen

Heaps, obwohl sie effizient sind, sind nicht die einzige Datenstruktur zur Handhabung von Daten. Hier ist ein kurzer Vergleich von Heaps mit anderen gängigen Datenstrukturen:

AVL-Bäume: Während Heaps auf Prioritäten abzielen, zielen AVL-Bäume darauf ab, das Gleichgewicht zu halten. Das bedeutet, dass AVL-Bäume garantieren, dass der Baum immer ausgewogen ist, was zu schnellen Such-, Einfüge- und Löschzeiten führt. Heaps garantieren jedoch nicht, dass die Daten vollständig sortiert sind.
Hashtabellen: Heaps und Hashtabellen haben unterschiedliche Zwecke. Hashtabellen sind darauf ausgelegt, den direkten Zugriff auf Daten basierend auf einem Schlüssel zu ermöglichen, während Heaps darauf ausgelegt sind, den Zugriff auf das höchste oder niedrigste Element zu priorisieren. Hashtabellen haben in der Regel eine konstante Zeitkomplexität für den Zugriff, während Heaps logaritmische Zeiten für Einfügungen und Löschungen aufweisen.
Rot-Schwarz-Bäume: Ähnlich wie AVL-Bäume sind Rot-Schwarz-Bäume Selbstausgleichsbäume. Sie stellen sicher, dass der Baum ausgewogen bleibt, aber sie verwenden Rotationen und Farbwechsel, um dies zu erreichen. Im Vergleich dazu sind Heaps einfacher in ihrer Struktur und in ihrer Funktion.

Heap-Infografik mit verschiedenen Datenstrukturen wie Heap, AVL-Baum, Hashtabelle und Rot-Schwarz-Baum

Erweiterte Heap-Operationen

Während grundlegende Operationen wie Einfügung und Entfernung ausreichen, um die meisten Anwendungen von Heaps zu unterstützen, gibt es auch erweiterte Operationen, die in speziellen Szenarien nützlich sein können:

Vereinigung von zwei Heaps

Dies ist der Prozess des Mischens von zwei Heaps, um einen neuen Heap zu erstellen, der alle Elemente aus beiden Heaps enthält.

Erhöhen eines Heap-Schlüssels

Bei dieser Operation wird der Wert eines Elements in einem Max-Heap erhöht und anschließend neu angeordnet, um die Heap-Eigenschaft wiederherzustellen.

Löschen eines beliebigen Elements

Anstatt nur das Wurzelelement zu löschen, kann man ein beliebiges Element im Heap löschen. Nach dem Löschen muss der Baum neu angeordnet werden, um die Heap-Eigenschaft zu gewährleisten.

Heap-Korrektur – Darstellung eines Heaps, das einen hervorgehobenen Fehler und dessen Korrektur zeigt

Heaps – Fehler und Problembehebung

Die Implementierung eines Heaps kann manchmal fehlerhaft sein. Einige häufige Fehler und deren Behebung sind:

Heap-Fehler beim Erhalten der Heap-Eigenschaft: Wenn nach einer Einfüge- oder Löschoperation die Heap-Eigenschaft nicht korrekt beibehalten wird, muss man sicherstellen, dass die Heapify-Funktion korrekt implementiert wurde.
Falsche Heap-Indizierung: Da Heaps in der Regel in einem Array gespeichert werden, kann eine falsche Indizierung dazu führen, dass auf falsche Kinder oder Elternteile zugegriffen wird. Stellen Sie sicher, dass Sie die richtigen Formeln für den Zugriff auf Eltern- und Kindknoten verwenden.
Heap-Speicherüberlauf: Wenn Sie versuchen, mehr Elemente in den Heap einzufügen, als Platz vorhanden ist, kann dies zu einem Speicherüberlauf führen. Implementieren.

Heap-Datenstruktur