Die Verwendung von Datenstrukturen ist auf dem Gebiet der Computerprogrammierung besonders wichtig, um Daten schnell und effizient zu speichern, zu verwalten und zu organisieren.
In dieser Erklärung geht es darum, was genau ein „Heap“ ist und wie er funktioniert.
Ein kleiner Hinweis für Dich: Die hier behandelten Datenstrukturen sind nicht zu verwechseln mit „Heap“ als Speicherbereich oder „Heap“ im Sinne von Garbage Collection. Es ist eine Datenstruktur, die verwendet werden kann, um einen Datensatz in einer quasi geordneten Reihenfolge zu halten.
Heap Definition
Ein Heap ist im Grunde ein spezieller binärer Baum. Also Elemente mit einer Baumstruktur. Es gibt Knoten, die jeweils höchstens zwei Kindknoten haben können. Jeder Knoten trägt eine Dateneinheit von allen auf dem Heap gespeicherten Daten.
Alle Ebenen des Baums sind immer vollständig gefüllt, mit Ausnahme der untersten Ebene, die von links nach rechts gefüllt wird. Daher darf dieser nur teilweise bestückt werden.
Im Kern ist der Heap (im Deutschen auch Halde genannt) eine erweiterte Baumdatenstruktur, die Programmierer hauptsächlich zum Implementieren und Sortieren von Warteschlangen verwenden.
Heaps sind binäre Bäume mit den folgenden Hauptmerkmalen:
- Die Eingabeebene im Heap wird bis auf die Blattknoten gefüllt.
- Alle Knoten haben maximal 2 untergeordnete (Kinder-)Knoten.
- Jeder Knoten befindet sich ganz links, d. h. jeder untergeordnete Knoten befindet sich links von seinem übergeordneten (Eltern-)Knoten.
Heap Eigenschaften
Es gibt viele Arten von Heaps, hier wird allerdings nur der einfachste Typ, der binäre Heap, betrachtet. Dabei gibt es zwei Varianten:
Mehr zum Binärbaum findest Du in einer eigenständigen Erklärung auf StudySmarter.
Max Heap
Jedes Element in Max Heap trägt tendenziell zur Max Heap-Eigenschaft bei. Das bedeutet, dass der Schlüssel des Elternknotens immer größer ist als der Schlüssel des Kindknotens. Die Max-Heap-Eigenschaft gibt an, dass für jeden Knoten bis zur Wurzel
A[PARENT(i)] ≥ A[i]
angewendet wird, d. h. das größte Element des Max-Heaps befindet sich an der Wurzel. In Abb. 1 kannst Du sehen, wie der Max Heap aussieht.
Min Heap
Das Min-Heap-Element verhält sich normalerweise entsprechend der Min-Heap-Eigenschaft. Dies unterscheidet sich stark von der Funktionsweise von Max Heap. Der Schlüssel des Elternknotens ist immer kleiner ist als der Schlüssel des Kindknotens.
Die Eigenschaft des Min Heap besagt, dass für jeden Knoten außer der Wurzel
A[PARENT(i)]≤A[i]
gilt, d. h. das kleinste Element des Min Heaps befindet sich an der Wurzel. All dies ist in Abb. 2 dargestellt.
Alle Heap-Operationen können sowohl auf dem Min-Heap als auch auf dem Max-Heap ausgeführt werden.
Heap Operatoren
Im Folgenden sind die Hauptoperationen aufgeführt, die beim Einschließen von Heap-Datenstrukturen verwendet werden.
| Heap-Operationen | Funktionsweise |
| getMax(): | Diese Operation gibt den maximalen Wert im Heap zurück. |
| Size: | Die Size-Operation wird verwendet, um die Größe des Heaps zu erhalten. |
extract: | Extract gibt den Wert eines Elements zurück und hilft, es aus dem Heap zu entfernen. |
delete: | Delete wird verwendet, um Elemente auf dem Heap zu entfernen. |
| insert: | Dieser Befehl fügt das Element in den Heap ein und behält seine Eigenschaften bei. |
| heapify: | Heapify ordnet die Elemente des Heaps neu an, um die Eigenschaften des Heaps beizubehalten. Die Funktion heapify() prüft, ob der untergeordnete Knoten kleiner als der übergeordnete Knoten ist. |
Heap Anwendung
Der Heap ist extrem gut darin, das größte oder kleinste Element in einem Array zu finden. Sie sind auch in statistischen und Auswahlalgorithmen nützlich. Die zeitliche Komplexität der Verwendung des Heaps zum Erreichen des Maximal- oder Minimalwerts ist O(1).
Programmierer entwerfen Prioritätswarteschlangen basierend auf der Heap-Struktur. Es dauert ungefähr O(log(n)), um jedes Element mit maximaler Effizienz in die Prioritätswarteschlange einzufügen und zu löschen.
Du findest eine eigenständige Erklärung zum Array auf StudySmarter!
Heap Sort
Sozusagen als Nebeneffekt bietet die Heap-Datenstruktur auch ein interessantes Sortierverfahren. HeapSort ist eine Methode zum Sortieren von Arrays. Da das Ausgabefeld in der Regel keine Heap-Eigenschaft besitzt, gliedert sich der Algorithmus in zwei Phasen:
- Aufbauphase: Eingabefeld A wird in einen Heap umgewandelt.
- Auswahlphase: Das Sortieren nach Auswahl wird unter Verwendung einer Heap-Struktur implementiert. Du musst sicherstellen, dass die Heap-Eigenschaften "dazwischen" gehalten werden.
Du kannst hier sehen, wie das in der Praxis funktioniert:
Mehr zu Heapsort findest Du in einer eigenständigen Erklärung auf StudySmarter!
Heap Vorteile und Nachteile
In der folgenden Tabelle findest Du die wichtigsten Pro- und Kontraseiten von Heaps.
| Vorteile | Nachteile |
| Der Heap hat globalen Zugriff auf Variablen. | Der Heap benötigt viel mehr Ausführungszeit als der Stack. |
| Heaps sind sehr nützlich, um maximale und minimale Zahlen zu finden. | Die für den Heap benötigte Rechenzeit ist im Allgemeinen länger. |
| Heaps sind in der Regel sehr flexibel und können in beliebiger Reihenfolge gelöscht oder neu zugewiesen werden. | Die Verwendung von Heap-Speicher kann die Speicherverwaltung sehr erschweren. |
Heap Speicher
Im Kontext der Speicherverwaltung auf Programmebene ist der Heap der Teil des Speichers, den das Betriebssystem laufenden Programmen zur Verfügung stellt.
Das kannst Du Dir im Grunde wie beim Dachboden eines Hauses vorstellen. Dort lassen sich nur mit einem begrenzten Platz Kisten verstauen – begrenzt ist das Ganze durch die Höhe (und Breite) des Raumes. Auf Prozessebene wäre das Speicherlimit der begrenzende Faktor.
Andererseits ist der Heap intern nicht einfach zu verwalten. Auf dem Heap erzeugter Speicher muss auch explizit freigegeben werden (je nach Programmiersprache durch den Programmierer oder z. B. den Garbage Collector).
Für den Zugriff auf den Heap werden Zeiger verwendet, obwohl dies nicht immer offensichtlich ist. Beispielsweise verwenden Java und C# Verweise auf Objekte, die sich auf dem Heap befinden. Natürlich musst Du im Hintergrund immer noch mit Zeigern arbeiten, die die Speicheradresse des Objekts enthalten.
Heap Variable
Jedem Thread im Programm wird ein eigener Speicherbereich mit einem Heap fester Größe zugewiesen. Dieser enthält Informationen über den Programmablauf (z. B. Funktionsparameter) und lokale Variablen. Wenn neue lokale Variablen erstellt werden, wächst der Heap und wenn der sichtbare Bereich ("Scope") bleibt, schrumpft der Heap wieder und der Speicher wird automatisch gelöscht.
Heap Overflow
Heap Overflow ist die zweite Generation der Pufferüberlauftechnologie. Genau genommen müsste diese Technik als Heap-Buffer-Overflow bezeichnet werden.
Buffer-Overflow ist eine der ältesten Hacking-Techniken. Es verwendet Eigenschaften der Von-Neumann-Architektur und der Programmiersprache C. Stack Overflow ist die erste Generation von Pufferüberläufen. Und in den meisten Fällen werden beide Begriffe als Synonyme verwendet.
Um die Grundlagen des Heap-Überlaufs zu verstehen, musst Du verstehen, wie der Heap verwaltet wird.
Speicher im Heap kann mithilfe von Bibliotheksfunktionen dynamisch zugewiesen werden. Dies geschieht normalerweise mit Funktionen wie:
- malloc()
- calloc()
- realloc()
Die eigentliche Verwaltung erfolgt durch die jeweilige Systembibliothek und ist abhängig von der Laufzeitumgebung.
Die Implementierung in die Systembibliothek erfolgt durch doppelt verkettete Listen, in denen freier und reservierter Speicher verwaltet wird. Die einzelnen Elemente einer verketteten Liste enthalten einen Header mit Verwaltungsinformationen und einen Speicherblock mit reservierten Daten.
Zwei Fehlerquellen können einen Heap-Überlauf verursachen:
- Die Größe des reservierten Speichers beim Datenladen ist statisch. Durch Anpassen der Daten (z. B. zu ladende Dateien) kannst Du sicherstellen, dass die Datenmenge größer ist als erwartet.
- Eine weitere Fehlerquelle ist, dass die bei der Reservierung benötigte Speicherberechnung falsch ist oder auf Angaben des Angreifers beruht.
Für einen erfolgreichen Heap-Overflow-Angriff muss man jedoch genau wissen, welche Heap-Implementierung das Programm zur Laufzeit verwenden wird.
Das Erstellen eines Heap-Überlaufs wird normalerweise dadurch erreicht, dass eine Datei geladen wird. Daher kann Schadcode über geladene Bilder, Dokumente, Spielstände, PDFs etc. ausgeführt werden.
Heap – Stack Unterschied
Stack ist ein Informatikbegriff, der sich auf eine dynamische Datenstruktur bezieht. Es kann von den meisten Mikroprozessoren unter Verwendung von Maschinenbefehlen direkt unterstützt werden.
Hier findest Du mögliche Unterschiede zwischen den Heap und Stack in tabellarischer Form.
| Heap | Stack |
| Auf dem Heap erstellte Objekte sind für alle Threads sichtbar. | Auf dem Stack gespeicherte Variablen sind nur für den besitzenden Thread sichtbar. |
| Der Heap gehört zu einer hierarchischen Datenstruktur. | Der Stack gehört zu einer linearen Datenstruktur. |
| Heaps können durch Arrays und Bäume dargestellt werden. | Stacks können auf drei Arten implementiert werden: basierend auf verknüpften Listen, dynamischem Speicher oder auf Arrays. |
| Nahezu jede Baumoperation kann auf den Heap angewendet werden: Gruppierung der Elemente und Ermittlung der Minimal- und Maximalwerte. | Die Operationen auf dem Stack sind push, pop und top. |
Wenn Du mehr über die Stapel-Datenstruktur erfahren möchtest, dann schau doch mal in der Erklärung zum "Stack" vorbei.
Nachweise
- vs.inf.ethz.ch: Heaps. (17.11.2022)
- hpi.de: Binäre Heaps und Heapsort. (17.11.2022)
- microsoft-press.de: Exploit! So schnell führt ein Programmierfehler zum Root-Zugriff. (17.11.2022)
Erklärungen 
Magazine 
