Open in App
Login Anmelden

Select your language

Suggested languages for you:
StudySmarter - Die all-in-one Lernapp.
4.8 • +11k Ratings
Mehr als 5 Millionen Downloads
Free
|
|
Heap

Die Verwendung von Datenstrukturen ist auf dem Gebiet der Computerprogrammierung besonders wichtig, um Daten schnell und effizient zu speichern, zu verwalten und zu organisieren.

Inhalt von Fachexperten überprüft
Kostenlose StudySmarter App mit über 20 Millionen Studierenden
Mockup Schule

Entdecke über 50 Millionen kostenlose Lernmaterialien in unserer App.

Illustration

Lerne mit deinen Freunden und bleibe auf dem richtigen Kurs mit deinen persönlichen Lernstatistiken

Jetzt kostenlos anmelden

Nie wieder prokastinieren mit unseren Lernerinnerungen.

Jetzt kostenlos anmelden
Illustration

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:

  • Min-Heap
  • Max-Heap

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-OperationenFunktionsweise
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:

  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:

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.

VorteileNachteile
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:

  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.

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.

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

Heap – Das Wichtigste

  • Heap Definition: Im Kern ist der Heap eine erweiterte Baumdatenstruktur, die Programmierer hauptsächlich zum Implementieren und Sortieren von Warteschlangen verwenden.
  • 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.
  • Heap Sort: Sozusagen als Nebeneffekt bietet die Heap-Datenstruktur auch ein interessantes Sortierverfahren.

    HeapSort ist eine Methode zum Sortieren von Arrays.

  • Heap Speicher: Im Kontext der Speicherverwaltung auf Programmebene ist der Heap der Teil des Speichers, den das Betriebssystem laufenden Programmen zur Verfügung stellt.
  • Heap Overflow ist die zweite Generation der Pufferüberlauftechnologie. Genau genommen müsste diese Technik als Heap-Buffer-Overflow bezeichnet werden.

Nachweise

  1. vs.inf.ethz.ch: Heaps. (17.11.2022)
  2. hpi.de: Binäre Heaps und Heapsort. (17.11.2022)
  3. microsoft-press.de: Exploit! So schnell führt ein Programmierfehler zum Root-Zugriff. (17.11.2022)

Häufig gestellte Fragen zum Thema Heap

Im Kontext der Speicherverwaltung auf Programmebene ist der Heap der Teil des Speichers, den das Betriebssystem laufenden Programmen zur Verfügung stellt. 

Der Heap gehört zu einer hierarchischen Datenstruktur. 

Der Stack gehört zu einer linearen Datenstruktur. 

Im Kern ist der Heap eine erweiterte Baumdatenstruktur, die Programmierer hauptsächlich zum Implementieren und Sortieren von Warteschlangen verwenden. 

Ein Heap, im Deutschen auch Halde genannt, ist eine Datenstruktur, die Daten kompakt organisiert und speichert und ein schnelles Einfügen und Löschen ermöglicht.

Finales Heap Quiz

Heap Quiz - Teste dein Wissen

Frage

Was ist ein Heap in der Informatik und im Computerwesen

Antwort anzeigen

Antwort

Ein Heap ist eine Datenstruktur, die in der Informatik verwendet wird, um Daten zu sortieren und Prioritätswarteschlangen zu erstellen.

Frage anzeigen

Frage

Wie wird der Heap größer

Antwort anzeigen

Antwort

Ein Heap kann sowohl als Baum als auch als Array dargestellt werden. Ein binärer Heap zum Beispiel ist ein binärer Baum. Jeder Knoten kann maximal zwei Kinder haben. Wie bei Baumstrukturen wächst der Heap von der Wurzel abwärts und von links nach rechts.

Frage anzeigen

Frage

Was ist ein Stack

Antwort anzeigen

Antwort

Ein Stack ist ein Begriff aus der Informatik, der sich auf eine dynamische Datenstruktur bezieht. Er kann von den meisten Mikroprozessoren, die Maschinenbefehle verwenden, direkt unterstützt werden.

Frage anzeigen

Frage

Was ist ein Heap?

Antwort anzeigen

Antwort

Im Kern ist der Heap eine erweiterte Baumdatenstruktur, die Programmierer hauptsächlich zum Implementieren und Sortieren von Warteschlangen verwenden.

Frage anzeigen

Frage

Was ist ein Heap Speicher

Antwort anzeigen

Antwort

Im Zusammenhang mit der Speicherverwaltung auf Programmebene ist der Heap der Teil des Speichers, den das Betriebssystem laufenden Programmen zur Verfügung stellt. 

Frage anzeigen

Frage

Was wird auf dem Heap gespeichert? 

Antwort anzeigen

Antwort

Ein Heap, im Deutschen auch Halde genannt, ist eine Datenstruktur, die Daten kompakt organisiert und speichert und ein schnelles Einfügen und Löschen ermöglicht. 

Frage anzeigen

Frage

Wahr oder Falsch

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.  

Antwort anzeigen

Antwort

Wahr

Frage anzeigen

Frage

Wahr oder Falsch

Sozusagen als Nebeneffekt bietet die Heap-Datenstruktur auch ein interessantes Suchalgorithmus. 

Antwort anzeigen

Antwort

Falsch

Frage anzeigen

Frage

Wahr oder Falsch

Heap Overflow ist die zweite Generation der Pufferüberlauftechnologie.  

Antwort anzeigen

Antwort

Wahr

Frage anzeigen

Frage

Wahr oder Falsch

Die einzigen Operationen auf dem Stack sind push, pop und insert. 

Antwort anzeigen

Antwort

Falsch

Frage anzeigen

Frage

Wahr oder Falsch

Nahezu jede Baumoperation kann auf den Heap angewendet werden: Gruppierung die Elemente und Ermittlung die Minimal- und Maximalwerte. 

Antwort anzeigen

Antwort

Wahr

Frage anzeigen

Frage

Ergänze

Der Heap gehört zu einer (1)                 Datenstruktur. 

Antwort anzeigen

Antwort

(1) hierarchische

Frage anzeigen

Frage

Ergänze

Heaps können durch (1)               und Bäume dargestellt werden.

Antwort anzeigen

Antwort

(1) Arrays

Frage anzeigen

Frage

Ergänze

Speicher im Heap kann mithilfe von (1)                   dynamisch zugewiesen werden.

Antwort anzeigen

Antwort

(1)Bibliotheksfunktionen

Frage anzeigen

Frage

Ergänze

(1)               Overflow ist die zweite Generation der Pufferüberlauftechnologie. 

Antwort anzeigen

Antwort

(1) Heap

Frage anzeigen

Frage

Ergänze

Programmierer entwerfen (1)                               basierend auf der Heap-Struktur. Es dauert ungefähr O(log(n)), um jedes Element mit maximaler (2)                      in die Prioritätswarteschlange einzufügen und zu löschen.

Antwort anzeigen

Antwort

(1) Prioritätswarteschlange

(2) Effizienz

Frage anzeigen

Teste dein Wissen mit Multiple-Choice-Karteikarten

Wahr oder FalschDer 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.  

Wahr oder FalschSozusagen als Nebeneffekt bietet die Heap-Datenstruktur auch ein interessantes Suchalgorithmus. 

Wahr oder FalschHeap Overflow ist die zweite Generation der Pufferüberlauftechnologie.  

Weiter

Karteikarten in Heap16

Lerne jetzt

Was ist ein Heap in der Informatik und im Computerwesen

Ein Heap ist eine Datenstruktur, die in der Informatik verwendet wird, um Daten zu sortieren und Prioritätswarteschlangen zu erstellen.

Wie wird der Heap größer

Ein Heap kann sowohl als Baum als auch als Array dargestellt werden. Ein binärer Heap zum Beispiel ist ein binärer Baum. Jeder Knoten kann maximal zwei Kinder haben. Wie bei Baumstrukturen wächst der Heap von der Wurzel abwärts und von links nach rechts.

Was ist ein Stack

Ein Stack ist ein Begriff aus der Informatik, der sich auf eine dynamische Datenstruktur bezieht. Er kann von den meisten Mikroprozessoren, die Maschinenbefehle verwenden, direkt unterstützt werden.

Was ist ein Heap?

Im Kern ist der Heap eine erweiterte Baumdatenstruktur, die Programmierer hauptsächlich zum Implementieren und Sortieren von Warteschlangen verwenden.

Was ist ein Heap Speicher

Im Zusammenhang mit der Speicherverwaltung auf Programmebene ist der Heap der Teil des Speichers, den das Betriebssystem laufenden Programmen zur Verfügung stellt. 

Was wird auf dem Heap gespeichert? 

Ein Heap, im Deutschen auch Halde genannt, ist eine Datenstruktur, die Daten kompakt organisiert und speichert und ein schnelles Einfügen und Löschen ermöglicht. 

Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!

Die erste Lern-App, die wirklich alles bietet, was du brauchst, um deine Prüfungen an einem Ort zu meistern.

  • Karteikarten & Quizze
  • KI-Lernassistent
  • Lernplaner
  • Probeklausuren
  • Intelligente Notizen
Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App! Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!

Finde passende Lernmaterialien für deine Fächer

Melde dich an für Notizen & Bearbeitung. 100% for free.

Fang an mit StudySmarter zu lernen, die einzige Lernapp, die du brauchst.

Jetzt kostenlos anmelden
Illustration