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 im Baum immer in der Wurzel. Die beiden Unterbäume einer Wurzel im Heap bilden dabei wiederrum einen Heap gleicher Ordnung.

Repä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 man mithilfe jeder beliebigen Ordnung einen Heap aufbauen, in dieser Veranstaltung verwenden wir jedoch hauptsächlich < und >. Wenn nur von Heap die Rede ist, kann man von einem Min-Heap mit <-Ordnung ausgehen.

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 wiederrum 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

Das Entfernen der Wurzel geschieht durch das Ersetzen des ersten Elementes des Heaps durch das letzte Element. Die Wiederherstellung der Heap-Eigenschaft ist dann ein simples Tauschen des nun obersten Elementes mit den 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 dann 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.