imported>Carolus requiescat: Die letzte Textänderung von ~2025-44603-5 wurde verworfen und die Version 258088686 von Trelrokx wiederhergestellt. Wer ist denn wir? Bitte neutral und objektiv formulieren

2025-09-12T13:36:37Z

Die letzte Textänderung von ~2025-44603-5 wurde verworfen und die Version 258088686 von Trelrokx wiederhergestellt. Wer ist denn wir? Bitte neutral und objektiv formulieren

Neue Seite

{{Redundanztext
|3=Binärer Heap
|4=Heap (Datenstruktur)
|2=Mai 2025|1=[[Spezial:Beiträge/141.30.244.84|141.30.244.84]] 00:43, 13. Mai 2025 (CEST)}}
[[Datei:Min-heap-1.svg|mini|hochkant=1.7|Beispiel eines Min-Heaps]]
Ein '''{{lang|en|Heap}}''' (englisch wörtlich: ''Haufen'' oder ''Halde'') in der [[Informatik]] ist eine zumeist auf [[Baum (Graphentheorie)|Bäumen]] basierende [[Abstrakter Datentyp|abstrakte]] [[Datenstruktur]]. In einem Heap können Objekte oder Elemente abgelegt und aus diesem wieder entnommen werden. Sie dienen damit der Speicherung von [[Menge (Mathematik)|Mengen]]. Den Elementen ist dabei ein [[Nummerung|Schlüssel]] zugeordnet, der die Priorität der Elemente festlegt. Häufig werden auch die Elemente selbst als Schlüssel verwendet.

Über die Menge der Schlüssel muss daher eine totale [[Ordnungsrelation|Ordnung]] festgelegt sein, über welche die Reihenfolge der eingefügten Elemente festgelegt wird. Beispielsweise könnte die Menge der [[Ganze Zahl|ganzen Zahlen]] zusammen mit dem [[Vergleichsoperator]] < als Schlüsselmenge fungieren.

Der Begriff Heap wird häufig als bedeutungsgleich zu einem [[Binärbaum#Partiell geordneter Baum|partiell geordneten Baum]] verstanden (siehe Abbildung). Gelegentlich versteht man einschränkend nur eine besondere Implementierungsform eines partiell geordneten Baums, nämlich die Einbettung in ein [[Feld (Datentyp)|Feld]] (Array), als Heap.

Verwendung finden Heaps vor allem dort, wo es darauf ankommt, schnell ein Element mit höchster Priorität aus dem Heap zu entnehmen ([[Highest In – First Out|HIFO-Prinzip]]), beispielsweise bei [[Vorrangwarteschlange]]n.

== Operationen ==
Je nach Art unterstützen Heaps eine ganze Reihe von [[Operation (Informatik)|Operationen]]. Die wichtigsten Operationen sind:

=== Heapify ===
Heapify ist eine Operation, um die Elemente des Heaps neu anzuordnen, um die Heap-Bedingung aufrechtzuerhalten. Sie erfolgt, wenn ein bestimmter Knoten ein Ungleichgewicht im Heap verursacht. Die Heapify kann in zwei Methoden erfolgen:

''Up-Heapify'' folgt dem Bottom-Up-Ansatz. In diesem Fall wird geprüft, ob die Knoten die Heap-Bedingung erfüllen, indem man in Richtung der Wurzel geht, und wenn Knoten nicht die Heap-Bedingung erfüllen, werden bestimmte Operationen ausgeführt, damit der Baum der Heap-Bedingung folgt.

''Down-Heapify'' folgt dem Top-Down-Ansatz. In diesem Fall wird geprüft, ob die Knoten die Heap-Bedingung erfüllen, indem man in Richtung der Blätter geht, und bestimmte Operationen ausführt, um die Heap-Bedingung herzustellen.

=== Insert ===
Das Einfügen eines Elements in den Heap erfolgt, indem das neue Element an das Ende des Heaps gesetzt wird. Weil das neu eingesetzte Element die Eigenschaften des Heaps verzerren kann, wird die Operation ''Up-Heapify'' durchgeführt, um die Eigenschaften des Heaps in einem Bottom-up-Ansatz zu erhalten.

=== Remove ===
Das Entfernen eines Elements erfolgt, indem das gelöschte Element durch das letzte Element im Heap ersetzt wird. Dann wird das letzte Element aus dem Heap gelöscht. Nun wird das letzte Element an einer Stelle im Heap platziert. Es kann die Heap-Bedingung nicht erfüllen, sodass die Operation ''Down-Heapify'' durchgeführt wird, um die Eigenschaften des Heaps aufrechtzuerhalten.

=== Find-max oder Find-min ===
Das maximale Element im Max-Heap und das minimale Element im Min-Heap ist die Wurzel des Heaps.

=== Extract Min oder Extract Max ===
Diese Operation gibt das maximale Element im Max-Heap oder das minimale Element im Min-Heap zurück. Dieses Element ist die Wurzel des Heaps.

Daneben werden häufig auch die [[Operation (Informatik)|Operationen]] ''changeKey'' zum Anpassen des Schlüssels und ''merge'' zum Verschmelzen zweier Heaps bereitgestellt. Die Operation ''changeKey'' wird häufig durch die Nacheinanderausführung der Operationen ''remove'' und ''insert'' gebildet, wobei nach dem Entfernen und vor dem erneuten Einfügen der Schlüssel angepasst wird. In einigen Fällen bieten Heaps statt ''changeKey'' lediglich die Operation ''decreaseKey'' an, bei der der Schlüssel lediglich verkleinert werden darf.

== Heap-Bedingung ==
Man unterscheidet Heaps in Min-Heaps und Max-Heaps. Bei ''Min-Heaps'' bezeichnet man die Eigenschaft, dass die Schlüssel der Kinder eines Knotens stets größer als oder gleich dem Schlüssel ihres Elternknoten sind, als ''Heap-Bedingung''. Dies bewirkt, dass an der Wurzel des Baumes stets ein Element mit minimalem Schlüssel im Baum zu finden ist. Umgekehrt verlangt die Heap-Bedingung bei ''Max-Heaps'', dass die Schlüssel der Kinder eines Knotens stets kleiner als oder gleich die ihres Elternknoten sind. Hier befindet sich an der Wurzel des Baumes immer ein Element mit maximalem Schlüssel.

Mathematisch besteht der Unterschied zwischen beiden Varianten nur in ihrer gegensätzlichen [[Ordnungsrelation|Ordnung]] der Elemente. Da die Definition von ''auf-'' und ''absteigend'' rein willkürlich ist, ist es also eine Auslegungsfrage, ob es sich bei einer konkreten Implementierung um einen Min-Heap oder um einen Max-Heap handelt.

Oft kommt es auch vor, dass ein Heap die Heap-Eigenschaft in beiden Richtungen abbilden soll. In diesem Fall werden einfach zwei Heaps geschaffen, wobei der eine nach der Kleiner- und der andere nach der Größer-Relation anordnet. Eine derartige Datenstruktur wird dann '''Doppelheap''' oder kurz '''Deap''' genannt.

Bei der Verwendung von Doppel-Heaps ist zu beachten, dass nicht jede Implementierung von Heaps dabei ihr Laufzeitverhalten für die einzelnen Operationen behält. Zum Beispiel unterstützen [[Fibonacci-Heap]]s nur ein ''decreaseKey'' zum Verringern der Schlüssel mit amortisiert konstanter [[Laufzeit (Informatik)|Laufzeit]]. Ein allgemeineres ''changeKey'' zum Ändern des Schlüssels, welches man im Falle eines derartigen Doppel-Heaps benötigen würde, braucht aber amortisiert mindestens logarithmische Laufzeit.

Eine Variante von Heaps, die die Heap-Bedingung nur eingeschränkt bzw. in abgewandelter Form unterstützt, sind sogenannte [[Min-Max-Heap]]s. Dabei handelt es sich um Doppel-Heaps, die durch die abgewandelte Form der Heap-Bedingung die Daten in nur einem Baum halten können.

== Implementierung ==
[[Datei:Heap-as-array.svg|mini|Beispiel eines vollständigen binären Max-Heaps, der in einem [[Feld (Datentyp)|Feld]] (Array) gespeichert wird.]]
Heaps werden normalerweise mit einer impliziten Heap-Datenstruktur implementiert, bei der es sich um eine implizite [[Datenstruktur]] handelt, die aus einem [[Feld (Datentyp)|Feld]] (Array) fester Größe oder einem dynamischen Array besteht, wobei jedes Element den Knoten eines Baums darstellt, dessen Eltern-Kind-Relation implizit durch seinen Index definiert wird. Nachdem ein Element in einen Heap eingefügt oder aus einem Heap gelöscht wurde, kann die Heap-Eigenschaft verletzt werden und der Heap muss durch Austauschen von Elementen innerhalb des Arrays ausgeglichen werden.

In einer impliziten Heap-Datenstruktur enthält das erste oder letzte Element die [[Wurzel (Graphentheorie)|Wurzel]]. Die nächsten beiden Elemente des Arrays enthalten seine untergeordneten Elemente. Die nächsten vier Elemente enthalten die vier Kinder der beiden Kindknoten usw. Somit würden sich die Kinder des Knotens an Position n an den Positionen ''2n'' und ''2n + 1'' in einem Array mit Startindex 1 oder an den Positionen ''2n + 1'' und ''2n + 2'' in einem Array mit Startindex 0 befinden. Die Berechnung des Index des übergeordneten Knotens des Elements an Position n ist ebenfalls unkompliziert. Bei einem Array mit Startindex 1 befindet sich das übergeordnete Element an Position ''n / 2''. Bei einem Array mit Startindex 0 das übergeordnete Element an der Position ''(n - 1) / 2''. Dies ermöglicht das Durchlaufen des [[Baum (Datenstruktur)|Baums]] durch einfache Indexberechnungen. Das Ausbalancieren eines Heaps erfolgt durch Austauschen von Elementen, die nicht in Ordnung sind. Da wir einen Heap aus einem Array erstellen können, ohne zusätzlichen Speicher zu benötigen, kann [[Heapsort]] verwendet werden, um ein Array [[in-place]] zu sortieren.

Verschiedene Arten von Heaps implementieren die Operationen auf unterschiedliche Weise. Insbesondere erfolgt das Einfügen jedoch häufig durch Hinzufügen des neuen Elements am Ende des Heaps im ersten verfügbaren freien Platz. Dies verstößt im Allgemeinen gegen die Heap-Eigenschaft. Daher werden die Elemente nach oben verschoben, bis die Heap-Eigenschaft wiederhergestellt wurde. In ähnlicher Weise wird das Löschen der [[Wurzel (Graphentheorie)|Wurzel]] durchgeführt, indem die Wurzel entfernt und dann das letzte Element in die Wurzel eingefügt und zum Ausgleich gesiebt wird. Das Ersetzen erfolgt also durch Löschen der Wurzel und Einfügen des neuen Elements in die Wurzel und Durchsieben, wobei ein Aufwärtsschritt im Vergleich zum Absenken des letzten Elements gefolgt vom Aufsteigen des neuen Elements vermieden wird.

== Programmierung ==
Das folgende Beispiel in der [[Programmiersprache]] [[C++]] zeigt die Implementierung der wichtigsten [[Operation (Informatik)|Operationen]] für einen binären Min-Heap.<ref>GeeksforGeeks: [https://www.geeksforgeeks.org/binary-heap/ Binary Heap]</ref><syntaxhighlight lang="c++">
#include <iostream>

using namespace std;

void swap(int*, int*); // Hilfsfunktion, die zwei Elemente vertauscht

// Deklariert die Klasse für den Heap
class MinHeap
{
int* elements_; // Pointer auf das Array für die Elemente des Heap
int capacity_; // Maximale Größe des Heap
int size_; // Größe, die die Anzahl der Elemente des Heap speichert
public:
MinHeap(int);
~MinHeap();
void MinHeapify(int);
int getParent(int index) { return (index - 1) / 2; }
int getLeftChild(int index) { return 2 * index + 1; }
int getRightChild(int index) { return 2 * index + 2; }
int extractMinimum();
void decreaseKey(int, int);
int getMinimumKey() { return elements_[0]; }
void deleteKey(int);
void insertKey(int);
};

MinHeap::MinHeap(int capacity) // Konstruktor
{
size_ = 0;
capacity_ = capacity;
elements_ = new int[capacity];
}

MinHeap::~MinHeap() // Destruktor
{
delete[] elements_;
}

// Fügt einen neuen Schlüssel ein
void MinHeap::insertKey(int key)
{
if (size_ == capacity_) // Wenn Kapazität überschritten, Funktion verlassen
{
return;
}
size_++; // Erhöht die Größe des Heap um 1
int index = size_ - 1;
elements_[index] = key; // Fügt den Schlüssel am Ende ein
// Der eingefügte Schlüssel wird so lange nach oben geschoben, wie das übergeordnete Element kleiner ist. Damit wird sichergestellt, dass die Heap-Bedingung erfüllt ist.
while (index != 0 && elements_[getParent(index)] > elements_[index]) // Wenn das Elternelement größer als der Schlüssel ist, werden die Elemente vertauscht.
{
swap(&elements_[index], &elements_[getParent(index)]);
index = getParent(index); // Aktualisiert den Index des Schlüssels
}
}

// Verringert den Wert des Schlüssels mit dem gegebenen Index
void MinHeap::decreaseKey(int index, int value)
{
if (value >= elements_[index]) // Wenn der neue Wert nicht kleiner als der aktuelle Wert ist, Funktion verlassen
{
return;
}
elements_[index] = value;
while (index != 0 && elements_[getParent(index)] > elements_[index])
{
swap(&elements_[index], &elements_[getParent(index)]);
index = getParent(index);
}
}

// Entfernt das minimale Element vom Heap
int MinHeap::extractMinimum()
{
if (size_ <= 0)
{
return INT_MAX;
}
if (size_ == 1)
{
size_--;
return elements_[0];
}
// Speichert den minimalen Wert und entfernt ihn vom Heap
int root = elements_[0];
elements_[0] = elements_[size_ - 1];
size_--;
MinHeapify(0);
return root;
}

// Löscht den Schlüssel mit dem gegebenen Index
void MinHeap::deleteKey(int index)
{
decreaseKey(index, INT_MIN); // Setzt den Wert auf minus unendlich
extractMinimum();
}

// Rekursive Methode, die die Heap-Bedingung für den Teilbaum mit dem gegebenen Index herstellt. Es wird vorausgesetzt, dass die Teilbäume die Heap-Bedingung schon erfüllen.
void MinHeap::MinHeapify(int index)
{
int leftChild = getLeftChild(index);
int rightChild = getRightChild(index);
int rightIndex = index;
if (leftChild < size_ && elements_[leftChild] < elements_[index])
{
rightIndex = leftChild;
}
if (rightChild < size_ && elements_[rightChild] < elements_[rightIndex])
{
rightIndex = rightChild;
}
if (rightIndex != index)
{
swap(&elements_[index], &elements_[rightIndex]); // Vertauscht das Wurzel-Element mit dem Wurzel-Element des rechten Teilbaums
MinHeapify(rightIndex); // Aufruf der rekursiven Methode für den rechten Teilbaum
}
}

// Vertauscht zwei Elemente des Heap
void swap(int* element1, int* element2)
{
int element = *element1;
*element1 = *element2;
*element2 = element;
}
</syntaxhighlight>

== Varianten von Heaps ==
Es existieren zahlreiche Arten von Heaps mit unterschiedlich gutem [[Asymptotische Laufzeit|Laufzeitverhalten]] für die verschiedenen [[Operation (Informatik)|Operationen]], die sie zur Verfügung stellen. Beispiele für Heaps sind:

=== Binärer Heap ===
Ein [[binärer Heap]] kann effizient mit linearem Zeitaufwand in [[Landau-Notation|<math>O(n)</math>]] konstruiert werden, wobei <math>n</math> die Anzahl der Elemente aus der Eingabe bezeichnet. Folgende Operationen arbeiten auf einem Heap und haben eine [[Asymptotische Laufzeit|Worst-Case-Laufzeit]] von <math>O(\log n)</math>:
* ''insert'' – fügt ein neues Element in den Heap ein
* ''remove'' – entfernt ein Element
* ''extractMin'' – extrahiert das Element mit dem kleinsten Schlüssel
* ''decreaseKey'' – verringert den Schlüsselwert eines Elements
Die Operation ''getMin'' liefert das kleinste Element im Heap zurück und benötigt dafür konstanten Rechenaufwand.

=== Binomial-Heap ===
[[Binomial-Heap|Binomial-Heaps]] unterstützen effizient die Operationen
* ''insert'' – zum Einfügen eines Elementes,
* ''remove'' – zum Entfernen eines Elementes,
* ''extractMin'' – zur Rückgabe und zum Entfernen eines Elementes mit minimalem Schlüssel (=höchster Priorität),
* ''changeKey'' – zum Ändern des Schlüssels eines Elementes und
* ''merge'' – zum Verschmelzen zweier Heaps.
Alle Operationen lassen sich mit einer [[Asymptotische Laufzeit|Worst-Case-Laufzeit]] von <math>O(\log n)</math> implementieren, wobei ''<math>n</math>'' die Zahl der aktuell im Heap befindlichen Elemente ist.

=== Fibonacci-Heap ===
Ein [[Fibonacci-Heap]] ist ähnlich wie ein [[Binomial-Heap]] in einer [[Vorrangwarteschlange]] realisiert. Das heißt, dass Elemente mit festgelegter Priorität in beliebiger Reihenfolge [[Effizienz (Informatik)|effizient]] im Heap gespeichert werden können und stets ein Element mit höchster Priorität entnommen werden kann. Die Priorität der Elemente wird diesen durch [[Nummerung|Schlüssel]] aufgeprägt. Über der Menge der Schlüssel muss daher eine [[Totalordnung]] bestehen, wie sie zum Beispiel die Kleiner-Gleich-Relation über den [[Ganze Zahl|ganzen Zahlen]] darstellt.

Weitere Varianten sind der [[Min-Max-Heap]], der [[Linksbaum]], der [[Treap]] und der [[Radix Heap|Radix-Heap]].

Außerdem gibt es mit [[Soft Heap]]s eine Variante bei der ein besseres Laufzeitverhalten erreicht wird, indem ein bestimmter Anteil der Schlüssel verdorben werden kann. Diese verdorbenen Schlüssel haben nicht mehr ihren ursprünglichen Wert.

== Laufzeitverhalten ==
Die folgende Tabelle gibt die [[Laufzeit (Informatik)|Laufzeiten]] von verschiedenen Heaps bezüglich ihrer Operationen an.
{| class="wikitable"
|- style="background-color:#e9e9e9" |
! rowspan="2" | Operation
! [[Binärer Heap]]
! [[Binomial-Heap]]
! [[Fibonacci-Heap]]
!!colspan="2" | [[Pairing-Heap]]
! [[Linksbaum]]
! [[2-3-Heap]]
|- style="background-color:#e9e9e9" |
!
!
! amortisiert
! amortisiert
! amortisiert !!
|-
| extract-min
|| <math>\mathcal{O}(\log n)</math>
|| <math>\mathcal{O}(\log n)</math>
|| <math>\mathcal{O}(\log n)</math>
|| <math>\mathcal{O}(\log n)</math>
|| <math>\mathcal{O}(\log n)</math> ||<math>\mathcal{O}(\log n)</math>
|-
| remove
|| <math>\mathcal{O}(\log n)</math>
|| <math>\mathcal{O}(\log n)</math>
|| <math>\mathcal{O}(\log n)</math>
|| <math>\mathcal{O}(\log n)</math>
|| <math>\mathcal{O}(\log n)</math> ||<math>\mathcal{O}(\log n)</math>
|-
| insert
|| <math>\mathcal{O}(\log n)</math>
|| <math>\mathcal{O}(\log n)</math>
|| <math>\mathcal{O}(1)</math>
|| <math>\mathcal{O}(\log n)</math> (<math>\mathcal{O}(1)</math> vermutet)
|| <math>\mathcal{O}(1)</math> oder <math>\mathcal{O}(\log n)</math> ||<math>\mathcal{O}(\log n)</math>
|-
| decrease-key
|| <math>\mathcal{O}(\log n)</math>
|| <math>\mathcal{O}(\log n)</math>
|| <math>\mathcal{O}(1)</math>
|| <math>\mathcal{O}(\log n)</math> (<math>\mathcal{O}(1)</math> vermutet)
|| <math>\mathcal{O}(1)</math> oder <math>\mathcal{O}(\log n)</math> ||<math>\mathcal{O}(1)</math>
|-
| merge
|| <math>\mathcal{O}(n)</math>
|| <math>\mathcal{O}(\log n)</math>
|| <math>\mathcal{O}(1)</math>
|| <math>\mathcal{O}(\log n)</math> (<math>\mathcal{O}(1)</math> vermutet)
|| <math>\mathcal{O}(1)</math> oder <math>\mathcal{O}(\log n)</math> ||
|}

== Anwendung ==
Heaps haben ein breites Spektrum an Anwendungen. Häufig ist vor allem der Einsatz in [[Vorrangwarteschlange]]n, wie sie bei [[Server|Servern]] oder [[Betriebssystem|Betriebssystemen]] zur Festlegung der Ausführungsreihenfolge von Aufgaben benötigt werden.

Daneben gibt es aber auch Anwendungen, die nicht explizit den Einsatz von [[Warteschlange (Datenstruktur)|Warteschlangen]] verlangen. Allgemein stellt ein Heap eine ideale [[Datenstruktur]] für [[Greedy-Algorithmus|Greedy-Algorithmen]] dar, die schrittweise lokale optimierte Entscheidungen treffen. So wird zum Beispiel beim [[Sortierverfahren|Sortieralgorithmus]] [[Heapsort]] ein [[Binärer Heap]] zum Sortieren eingesetzt. [[Fibonacci-Heap]]s finden beim [[Algorithmus von Dijkstra]] bzw. [[Algorithmus von Prim|Prim]] Anwendung.

== Siehe auch ==
* [[Liste (Datenstruktur)]]
* [[Menge (Datenstruktur)]]
* [[Stapelspeicher]]

== Literatur ==
* {{BibISBN|0262032937|Seite=127}}
* {{BibISBN|0201896850|Seite=144–155}}

== Weblinks ==
{{Commonscat|Heap data structures|Heaps}}

== Einzelnachweise ==
<references />

[[Kategorie:Datenstruktur]]

Heap (Datenstruktur) - Versionsgeschichte

imported>Carolus requiescat: Die letzte Textänderung von ~2025-44603-5 wurde verworfen und die Version 258088686 von Trelrokx wiederhergestellt. Wer ist denn wir? Bitte neutral und objektiv formulieren