Heap

Ein Heap ist eine Datenstruktur, die aus „Knoten“ besteht, die Werte enthalten. Ein typischer Heap hat oben einen Wurzelknoten, unter dem sich direkt zwei oder mehr untergeordnete Knoten befinden können. Jeder Knoten kann zwei oder mehr untergeordnete Knoten haben, wodurch der Heap mit jedem untergeordneten Knoten breiter wird. In einer visuellen Darstellung sieht ein Heap wie ein auf dem Kopf stehender Baum aus, und seine allgemeine Form ähnelt einem Haufen.

Während jeder Knoten in einem Heap zwei oder mehr untergeordnete Knoten haben kann (auch „Kinder“ genannt), beschränken die meisten Heaps jeden Knoten auf zwei Kinder. Diese Arten von Heaps werden auch als binäre Heaps bezeichnet und können zum Speichern sortierter Daten verwendet werden. Ein „binärer Max-Heap“ speichert beispielsweise den höchsten Wert im Wurzelknoten. Die zweithöchsten und dritthöchsten Werte werden in den untergeordneten Knoten des Wurzelknotens gespeichert. Im gesamten Baum hat jeder Knoten einen höheren Wert als jeder seiner untergeordneten Knoten. Ein „binärer Min-Heap“ ist das Gegenteil: Der Wurzelknoten speichert den niedrigsten Wert, und jeder Knoten hat einen niedrigeren Wert als seine untergeordneten Knoten.

In der Informatik werden Heaps häufig als einfache Diagramme dargestellt. Das tatsächliche Speichern von Daten in einem Heap ist jedoch komplexer. Um einen Heap zu erstellen, müssen Programmierer einzelne Algorithmen zum Einfügen und Löschen von Daten schreiben. Die in einen Heap eingefügten Werte werden normalerweise in einem Array gespeichert, auf das ein Programm zugreifen kann. Da die Daten in einem Heap bereits sortiert sind, bietet er eine effiziente Möglichkeit, nach bestimmten Werten zu suchen.

NOTE: „Der Heap“ ist außerdem ein Programmierbegriff, der zum Beschreiben von dynamisch zugewiesenem Speicher verwendet werden kann. Auf diesen Speicherblock können aktive Anwendungen zugreifen. Da Speicher im Heap dynamisch zugewiesen wird, kann er je nach verwendeter Speichermenge wachsen oder schrumpfen.