Binärer Heap

2025-05-12T22:43:45Z

141.30.244.84: Redundanz

{{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:Binary heap indexing.png|mini|Binärer ''Min-Heap'']]
Ein '''Binärer [[Heap (Datenstruktur)|Heap]]''' ist eine [[Datenstruktur]] aus der [[Informatik]] zum [[Effizienz (Informatik)|effizienten]] [[Sortieren]] von Elementen. Das asymptotisch optimale [[Sortierverfahren]] [[Heapsort]] verwendet als zentrale Datenstruktur einen binären Heap. Des Weiteren wird der binäre Heap zur Implementierung einer [[Vorrangwarteschlange]], in der das Element mit der höchsten Priorität effizient abgefragt und entfernt werden kann, verwendet.
Die Priorität der Elemente wird diesen durch [[Nummerung|Schlüssel]] aufgeprägt. Über der Menge der Schlüssel muss daher eine totale [[Ordnungsrelation|Ordnung]] bestehen, wie sie zum Beispiel die Kleiner-Relation (<) über den [[Ganze Zahl|ganzen Zahlen]] darstellt.

In der Literatur wird oft der Zusatz ''binär'' weggelassen, so dass je nach Zusammenhang der ''Heap'' als archetypische (binäre) Heap-Struktur (implementiert in einem Array) oder die Klasse aller [[Heap (Datenstruktur)|Heap-Datenstrukturen]] gemeint ist.
Des Weiteren wird bei Verwendung der Ordnungsrelation <math><</math> bzw. <math>></math> ein Heap als ''Min-Heap'' bzw. ''Max-Heap'' bezeichnet.
Da sich die Operationen im Min- und Max-Heap nur durch die verwendete Ordnungsrelation unterscheiden, wird im Folgenden der binäre Heap und die Operationen darauf am Beispiel des Min-Heap definiert.

== Definition Min-Heap ==

Ein [[Binärbaum]] <math>H</math> ist ein Min-Heap, wenn für jeden Knoten <math>i</math> mit <math>i\neq\text{root}</math> gilt:

<math>\text{key}(H, i) \geq \text{key}(H, \text{parent}(i))</math>

Wobei <math>\text{parent}(i)</math> den [[Gewurzelter Baum#Weitere Begriffe|Elternknoten]] von <math>i</math> bezeichnet.

Diese Eigenschaft wird als (Min-)Heap-Eigenschaft bezeichnet.

Ein Heap ist also ein [[Binärbaum#Partiell geordneter Baum|partiell geordneter Baum]]. Zwischen Kinder- und Eltern-Knoten besteht eine Ordnung, aber die Kinder-Knoten sind nicht untereinander geordnet.

== Operationen ==
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.

== Struktur ==
Ein Binärer Heap besteht aus einem [[Binärbaum]], bei dem alle Schichten bis auf die letzte vollständig aufgefüllt sein müssen. Die letzte Schicht des Baumes muss linksbündig aufgefüllt werden. Diese Struktur garantiert, dass der Baum [[Balancierter Baum|balanciert]] ist.

Zusätzlich muss der Binärbaum die Heap-Bedingung erfüllen: am Beispiel des Min-Heaps (siehe Abbildung) muss der Schlüssel jedes [[Kindknoten|Kindes]] eines Knotens größer-gleich dem Schlüssel des Knotens selbst sein. Die Heap-Eigenschaft garantiert, dass sich an der [[Wurzel (Graphentheorie)|Wurzel]] immer der Knoten mit dem kleinsten Key befindet.

Häufig wird ein Binärer Heap nicht explizit mit Zeigern konstruiert, sondern durch ein Array abgebildet. Will man einen Binären Heap in einem [[Feld (Datentyp)|Array]] speichern, so wird die Wurzel des Baums an der ersten Position im Array gespeichert. Bei einer Array-Indizierung beginnend mit <math>1</math> werden die beiden Nachfolger des Knotens an der <math>i</math>-ten Position an der <math>2i</math>-ten und <math>2i+1</math>-ten Position gespeichert, entsprechend der [[Kekule-Nummer]]ierung. Analog dazu sind die Nachfolger des Knotens mit Index <math>i</math> an der <math>2i+1</math>-ten und <math>2i+2</math>-ten Position gespeichert, wenn die Array-Indizierung mit 0 beginnt.

[[Datei:Binary tree array.svg|500px|zentriert|mini|Beispiel für die implizite Darstellung eines Binärbaums in einem Array. Die eingezeichneten Pfeile sind implizit durch die Funktionen für die Berechnung der Kinder bzw. Eltern-Indizes gegeben.]]

== Algorithmen ==

Bei der Analyse der Algorithmen wird die Heapgröße bzw. die Anzahl der Elemente im Heap-Array mit <math>n</math> bezeichnet.

=== Heapify ===

Die Basis mehrerer Heap-Operationen bildet die Funktion ''heapify''. Sie stellt gegebenenfalls die Heap-Bedingung eines Binärbaums wieder her, vorausgesetzt, dass der linke und der rechte Teilbaum die Heap-Bedingung erfüllen. Dazu tauscht ''heapify'' solange rekursiv absteigend Kind- mit Eltern-Knoten, bis die Heap-Eigenschaft nicht mehr verletzt ist.

Anders formuliert, wenn einer der beiden Kindknoten zur aktuell betrachteten Elternebene aufsteigt, sinkt der Elternknoten in der Folge rekursiv so weit herab, bis er die Ebene seines Gewichtes erreicht hat. Wegen des sukzessiven Tauschens (oder „Schiebens“) von einem Knoten in einen Teilbaum herab, wird die ''heapify'' Operation auch als ''sift-down'' ([[Sieben (Klassierverfahren)|„Sieben“]]) bzw. Sift-Down-Phase bezeichnet.

In [[Pseudocode]]:

<syntaxhighlight lang="C">
void heapify(Array H, int i)
assert(isheap(H, left(i)) && isheap(H, right(i)))
int min = i
if (left(i) < H.size && H.key(left(i)) < H.key(min))
min = left(i)
if (right(i) < H.size && H.key(right(i)) < H.key(min))
min = right(i)
if (min != i) {
H.swap(i, min)
heapify(H, min)
}
</syntaxhighlight>

Die Hilfsfunktionen ''left'' bzw. ''right'' berechnen den Index des linken bzw. rechten Kind-Knotens im Heap-Array, ''key'' abstrahiert von dem Zugriff auf dieses Array und ''swap'' vertauscht zwei Elemente in dem Array, in dem der Heap gespeichert ist. Die Funktion traversiert den Baum nur in die Tiefe, so dass ihre Laufzeit in <math>O(\text{height}(H))</math> ist. Da die Höhe des Baums logarithmisch von der Anzahl seiner Elemente abhängt, benötigt die Funktion ''heapify'' im Worst-Case logarithmische Laufzeit bzgl. der Größe des Heaps, also <math>O(\log n)</math>. ''heapify'' benötigt nur eine konstante Anzahl zusätzlicher Speicherzellen, weil sie [[Endrekursion|tail rekursiv]] ist. Das heißt, dass die Rekursion manuell oder automatisch durch eine Schleife ohne Stack ersetzt werden kann:

<syntaxhighlight lang="C">
void heapify(Array H, int a)
int i = a
do {
assert(isheap(H, left(i)) && isheap(H, right(i))
int min = i
if (left(i) < H.size && H.key(left(i)) < H.key(min))
min = left(i)
if (right(i) < H.size && H.key(right(i)) < H.key(min))
min = right(i)
if (min == i)
break
H.swap(i, min)
i = min
} while(true)
</syntaxhighlight>

=== Build ===

Die Funktion ''build'' konstruiert einen Heap aus einem Array, indem sie iterativ die Funktion ''heapify'' aufruft. Sie beginnt bei den Blättern, die per Definition die Heap-Eigenschaft erfüllen, und arbeitet sich schrittweise zur Wurzel vor. Diese Arbeitsweise wird auch als bottom-up bezeichnet. Als Pseudocode:

<syntaxhighlight lang="C">
void build(Array a)
if (a.empty)
return
for (int i = a.size/2-1; i>=0; --i)
heapify(a, i)
</syntaxhighlight>

Aus der Struktur des binären Heap, der in einem Array gespeichert ist, ergibt sich, dass ab Position <math>n/2-1</math> nur noch Blätter, also 1-elementige Heaps, gespeichert sind. Das heißt ab <math>n/2-1</math> beginnt die unterste Ebene (Level) des binären Baums. Da die Baumelemente im Array in [[Binärbaum#Traversierung|level-order]] gespeichert sind, läuft die Iteration sukzessive jeweils vom letzten bis ersten Elements eines Levels.

Die Laufzeit von ''build'' ist in <math>O(n)</math>, was nicht direkt offensichtlich ist. Denn ''heapify'' ist in <math>O(\log n)</math> und wird <math>n</math>-mal aufgerufen. Die lineare Laufzeit ergibt sich aus folgender Gleichung:

<math>\sum_{h=0}^{\left\lfloor\log n\right\rfloor} \left\lceil \frac{n}{2^{h+1}} \right\rceil O(h) = O\left(n \sum_{h=0}^{\left\lfloor\log n\right\rfloor} \frac{h}{2^h} \right) = O(n)</math>

wobei <math>h</math> über die Baumhöhe iteriert und <math>\frac{n}{2^{h+1}}</math> die Anzahl der Teilbäume auf Level <math>h+1</math> bzw. die Anzahl der Kinder aller Knoten der Höhe <math>h</math> berechnet.

=== Decrease-Key ===

Wird der Schlüssel eines Heap-Elements <math>i</math> verringert, so muss gegebenenfalls die Heap-Eigenschaft in den Vorgängerknoten wiederhergestellt werden.
Die Heap-Eigenschaft in den Kinder-Teilbäumen von <math>i</math> wird durch die ''decrease-key'' Operation nicht verändert. ''decrease-key'' arbeitet wie ''build'' bottom-up:

<syntaxhighlight lang="C">
void decrease(Array H, int i, newkey)
assert(isheap(H, 0))
assert(H.key(i) >= newkey)
H.key(i) = newkey
while (i > 0 && H.key(i) < H.key(parent(i)))
H.swap(i, parent(i))
i = parent(i)
</syntaxhighlight>

=== Insert ===

Das Einfügen eines Elementes mittels ''insert'' erfolgt, indem das Heap-Array um ein neues Element am Ende mit dem Wert <math>\inf</math> erweitert wird, worauf die Funktion ''decrease'' mit dem einzufügenden Schlüssel aufgerufen wird, damit die möglicherweise verletzte Heap-Eigenschaft wieder hergestellt wird:

<syntaxhighlight lang="C">
void insert(Array H, newkey)
assert(isheap(H))
int i = H.size
H.resize(i+1)
H.key(i) = inf
decrease(H, i, newkey)
</syntaxhighlight>
Die Laufzeit ist entsprechend <math>O(\log n)</math>.

=== Remove ===

Das Entfernen eines Elementes mittels ''remove'' geschieht, indem das zu entfernende Element aus seiner Position ''i'' im Heap entfernt und an seine Stelle das sich am Ende des Heaps befindende Element gesetzt wird. Anschließend muss die Heap-Eigenschaft an Position ''i'' wiederhergestellt werden. Dabei kann es sowohl vorkommen, dass das Element auf Position ''i'' größer ist als sein Elternknoten, als auch dass es kleiner ist. Dementsprechend muss es mittels ''heapify'' nach unten oder mittels ''decrease'' nach oben verschoben werden.

Der ''decrease''-Fall mag nicht offensichtlich sein. Wieso sollte das vormals letzte Element des Arrays kleiner sein als ein viel weiter oben im Baum gelöschtes Element? Das liegt daran, dass ein Heap nur eine partielle und keine totale Ordnung repräsentiert. Betrachtet man den ersten gemeinsamen Vorfahren von zu löschendem und letztem Element, so kann es sein, dass sich in dem einen Teilbaum mit dem letzten Element nur sehr kleine Elemente befinden, wohingegen der andere Teilbaum mit dem zu löschenden Element größere Elemente enthält. Hier ist ein Beispiel einer solchen Situation. Das Element mit dem Index ''5'' soll gelöscht werden:

h1 = [0, 1, '''2''', 2, 1, '''''2''''', 2, 2, 2, '''1'''] // ist ein korrekter Heap<br/>
-> [0, 1, '''2''', 2, 1, '''1''', 2, 2, 2, '''''2'''''] // nach dem Swap mit dem letzten Element<br/>
-> [0, 1, '''2''', 2, 1, '''1''', 2, 2, 2] // nach dem Entfernen des nun letzten Elements

Nach dem Entfernen des letzten Elements verletzt das sich jetzt an Index 5 befindende Element '''1''' zusammen mit seinem Elternknoten '''2''' die Heap-Eigenschaft. Ein Anwenden von ''heapify'' würde das Array nicht ändern, da die Funktion nur Elemente nach unten schiebt. Bei Index 5 handelt es sich aber bereits um einen Blatt-Knoten. Stattdessen müssen wir das Element an Position 5 nach oben schieben. Dies geschieht mit der Funktion ''decrease''.

<syntaxhighlight lang="c">
Element remove(Array H, unsigned int i)
assert(isheap(H))
assert(i<H.size)
removedItem = H[i]
int lastIdx = H.size-1
H.swap(i,lastIdx)
H.resize(lastIdx)
/* Im Fall i == lastIdx wurde die Heap-Eigenschaft durch das Entfernen
des Elements beibehalten, und i befindet sich nun ''out of bounds'',
weil das Array verkleinert wurde. Ein Aufruf von heapify oder
decrease würde zum Absturz führen. */
if ( i != lastIdx ) {
if ( i == 0 || H.key(i) > H.key(parent(i)) ) {
heapify(H, i)
} else {
decrease(H, i, H.key(i)) // decrease macht nichts, wenn H.key(i) == H.key(parent(i))
}
}
return removedItem
</syntaxhighlight>

=== Extract-Min ===

Das Zurückgeben und Entfernen eines Elementes mittels ''extractMin'' gestaltet sich ähnlich wie ''remove''. Das minimale Element befindet sich wegen der Heap-Bedingung an der Wurzel des Baumes und stellt damit das zu entfernende Element dar:

<syntaxhighlight lang="C">
Element extractMin(Array H)
assert(isheap(H))
assert(H.size > 0)
return remove(H, 0)
</syntaxhighlight>
Die Laufzeit ist entsprechend: <math>O(\log n)</math>

=== Get-Min ===

Die ''getMin'' gibt das kleinste Element in einem Heap zurück.
Aus der Heap-Eigenschaft folgt direkt, dass das kleinste Element immer an der ersten Array-Position, also der Wurzel des binären Baums steht. Im Pseudo-Code:

<syntaxhighlight lang="C">
Element getMin(Array H)
assert(isheap(H))
assert(H.size > 0)
return H.key(0)
</syntaxhighlight>
Die Laufzeit ist entsprechend konstant: <math>O(1)</math>

== Siehe auch ==
* [[Binomial-Heap]]
* [[Fibonacci-Heap]]

== Literatur ==

* {{BibISBN|0262032937|Seite=127}}
* {{BibISBN|0201896850|Seite=144}}

{{SORTIERUNG:Binarer Heap}}
[[Kategorie:Datenstruktur]]

Wikipedia (Deutsch) – Lokale Kopie - Benutzerbeiträge [de]

Binärer Heap