Heap

Ein Heap ist eine besondere Form des Binären Baumes. Je nach auf dem Heap verwendeter Ordnung spricht man von einem Min-, oder von einem Max-Heap.

Ordnung

Der Aufbau eines Heaps wird durch seine Ordnung bestimmt. Häufig verwendet werden < (kleiner) und > (größer). Der sogenannt Max-Heap hat eine >-Ordnung. Hierbei steht das größte Element des Baumes in der Wurzel. In dieser Veranstaltung wird jedoch, wenn nicht weiter spezifiziert, von einem Min-Heap ausgegangen. Dieser hat eine <-Ordnung, in der Wurzel steht folglich immer das kleinste Element.

Die Ordnung des Heaps gilt auch für seine Unterbäume.

Repräsentation

Ein Heap wird meistens in Form eines Arrays gespeichert. Dabei wird, zum einfacheren Rechnen, das Element mit dem Index 0 im Array frei gelassen. Das Kind eines Knotens mit dem Index i kann dann in den Einträgen2i und 2i + 1 gespeichert und gefunden werden. Entsprechend ist der Elternknoten eines Knotens i der Eintrag im Array mit dem Index i/2.

Eigenschaften

Jeder Heap hat folgende Eigenschaften:

• Ein Heap ist ein linksvollständiger Binärbaum.
• Das Element mit dem kleinsten Wert steht in der Wurzel.
• Jeder Unterbaum ist wiederum ein Heap.

Operationen

Auf einem Heap sind folgende Operationen üblich:

• Entfernen der Wurzel
• Einfügen eines neuen Elementes
• Wiederherstellung der Heap-Eigenschaften

Entfernen der Wurzel

Durch das Entfernen der Wurzel erhält man das kleinste Element.

Das Entfernen der Wurzel geschieht durch das Ersetzen des ersten Elementes des Heaps (also der Wurzel) durch das letzte Element (also in der untersten Ebene ganz rechts).

Im Anschluss müssen direkt die Heap-Eigenschaften wiederhergestellt werden. Dies geschieht durch den Tausch der neuen "Wurzel" mit dem kleineren ihrer beiden Kinder. Diese Methode nennt man heapify.

Durch das wiederholte Entfernen der Wurzel erhält man also nach und nach zuerst das kleinste, dann das zweitkleinste, dann das drittkleinste, usw. Element. Diese Sortierung wird als Heapsort bezeichnet.

Einfügen eines neuen Elementes

Das Einfügen geschieht durch Anfügen des neuen Elementes an die erste freie Stelle im Heap. Da der Heap linksvollständig ist, ist dieses neue Element damit das letzte Element im Heap.

Anschließend wird der Heap auf seine Eigenschaften überprüft. Ist das neue Element kleiner als sein Elternteil, wird es mit diesem getauscht. Das neue Element wandert so lange nach oben, bis die Heap-Eigenschaften wiederhergestellt sind. Ein Vergleich mit den Geschwisterknoten ist nicht notwendig. Da das Elternteil immer kleiner als seine Kinder ist, muss ein neues Element, falls es kleiner als sein Elternteil ist, logischerweise auch kleiner als seine Geschwister sein.

Wiederherstellung der Heap-Eigenschaften

Wird ein Element hinzugefügt oder entfernt, muss entweder das neue letzte Element nach oben im Baum bewegt werden, oder, beim Entfernen, die neue Wurzel nach unten. Da in jedem Unterbaum die Heap-Eigenschaften bestehen, funktioniert das alles problemlos, solange die verwendete Struktur zu Beginn wirklich ein Heap gewesen ist.