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.

In EINI gehen wir jedoch davon aus, dass ein Heap ein Min-Heap ist. Dabei steht das kleinste Element des Baumes immer in der Wurzel. Die beiden Unterbäume einer Wurzel im Heap bilden dabei wiederum einen Heap gleicher Ordnung.

Repräsentation

Ein Heap wird zumeist in Form eines Arrays gespeichert. Dabei wird meistens, zum Zwecke einfacherer Rechnungen, das Element mit dem Index 0 im Array frei gelassen. Ein Kindknoten 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.

Ordnung

Theoretisch kann mithilfe jeder beliebigen Ordnung ein Heap aufgebaut werden. In dieser Veranstaltung verwenden wir jedoch hauptsächlich < und >. Wenn nur von Heap die Rede ist, kann man von einem Min-Heap ausgehen. Dieser hat immer eine <-Ordnung.

Eigenschaften

Die Eigenschaften eines Heaps sind folgendermaßen definiert:

• Ein Heap ist ein links-vollständiger Binärbaum.
• Das Element mit dem kleinsten (größten, ...) 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

Je nach Ordnung des Heaps erhält man durch das Entfernen der Wurzel entweder das kleinste oder größte Element.

Das Entfernen der Wurzel geschieht durch das Ersetzen des ersten Elementes des Heaps (also der Wurzel) durch das letzte Element (also unten rechts in der graphischen Darstellung).

Die Wiederherstellung der Heap-Eigenschaft ist dann ein simples Tauschen des jeweiligen nun obersten Elementes mit dem kleineren seiner beiden Kinder, bis die Heap-Eigenschaft im ganzen Baum wiederhergestellt ist.

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 links-vollständig ist, ist dieses Element damit das letzte Element im Heap. Anschließend muss dieses Element im Baum unter Umständen nach oben wandern, damit die Heap-Eigenschaft wieder gelten kann. Dabei muss jedoch immer nur mit dem Vater verglichen werden. Da der Vater garantiert kleiner ist als sein potentiell anderes Kind, wird bei einem Tausch das nach oben getauschte Element auch kleiner sein als sein Geschwisterknoten, da er sonst nicht getauscht worden wäre.

Wiederherstellung der Heap-Eigenschaften

Wird ein Element hinzugefügt oder entfernt, muss entweder das neue letzte Element nach oben im Baum bewegt werden, oder die neue Wurzel beim Entfernen nach unten. Da in jedem Unterbaum die Heap-Eigenschaften bestehen, sind relativ wenige Spezialfälle zu beachten.