Nach Einfügen und Löschen ist es möglich, dass die Heap-Eigenschaft
(Ordnung) gestört ist.
Um diese Eigenschaft wiederherzustellen
verwendet man zwei Funktionen.
Zum einem „siftup“ für das Einfügen und zum anderen „siftdown“ für das Löschen.
Beide benötigen ungefähr log n Schritte um den Heap zu reparieren.
„siftup“ - Funktion:
Das einzufügende Element wird als rechtestes Blatt dem Heap
hinzugefügt.
Da die Heap-Eigenschaft nur zwischen dem aktuellen
Knoten und seinem Vater gestört sein kann, werden beide
Schlüsselwert miteinander verglichen und gegebenenfalls vertauscht.
Dies wird solange wiederholt, bis keine Vertauschung mehr nötig
ist bzw. die Wurzel erreicht wurde.
Der eingefügte Knoten steigt also in Bottom-Up-Manier zu seiner
korrekten Position auf.
„siftdown“ - Funktion:
Beim Löschen wird der Wert der Wurzel ausgegeben und anschließend
durch den Wert des rechtesten Blattes ersetzt.
Das „leere“ Blatt wird gelöscht.
Die Heap-Eigenschaft kann nun zwischen dem aktuellen Knoten
und seinen Söhnen gestört sein. Bei Bedarf wird mit dem kleinsten
der beiden Söhne (falls vorhanden) getauscht. Mit kleinster Sohn ist
der Knoten, mit dem kleinsten Wert gemeint.
Es wird solange getauscht bis keine Vertauschung mehr nötig ist
bzw. ein Blatt erreicht ist.
Die Wurzel sinkt also auf die korrekte Position ab.