Heap

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.

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

• Min-Heap
• Max-Heap

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.

Heap Operatoren

Im Folgenden sind die Hauptoperationen aufgeführt, die beim Einschließen von Heap-Datenstrukturen verwendet werden.

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.

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:

1. Aufbauphase: Eingabefeld A wird in einen Heap umgewandelt.
2. 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:

Heap Vorteile und Nachteile

In der folgenden Tabelle findest Du die wichtigsten Pro- und Kontraseiten von Heaps.

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).

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.

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:

1. 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.
2. 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.

Heap – Stack Unterschied

Hier findest Du mögliche Unterschiede zwischen den Heap und Stack in tabellarischer Form.