Heapsort erklären?

[Woyzeck]

hallo,

hab das Video jetzt nicht zuende geschaut. Aber grundsätzlich macht man beim Heapsort 3 Schritte.

Im ersten Schritt wird das Array oder die Liste oder wo auch immer deine Daten drinstehen sequenziell in einen Binärbaum "eingetragen". (Das macht man natürlich nur in Gedanken. Beim Programmieren ist der Heap ja weiterhin ein Feld) Stichwort: sequentielle Darstellung eines Binärbaums.

Nun kommt der zweite Schritt: Das Herstellen der Heapeigenschaft.
Hierzu muss immer der parent-Knoten größer sein, als seine Kinder.
Dazu gehst du dein Feld von hinten bzw. deinen Baum/Heap von unten durch und suchst ein Element, das kleiner ist als sein Vorgänger. Ist das der Fall tauschst du und fängst wieder von hinten an, nach Verletzungen der Heapeigenschaft zu suchen.

Jetzt folgt der dritte Schritt: Nun hat man ja das größte Element in der Wurzel stehen, also tauscht man das mit dem letzten Element (Im ersten Schritt ist das das Element ganz unten rechts). Nun musst du die Wurzel "einsinken" lassen, da sie ja nicht mehr das größte Element ist. Du vergleichst also mit den Kindern und tauscht mit dem größeren der Kinder, damit die Heapeigenschaft wieder hergestellt wird. Das machst du so lange, bis die neue Wurzel an einem Punkt angekommen ist, wo die Kinder beide kleiner sind.

Das letzte Element steht nun an seiner richtigen Position.

Danach tauschst du die Wurzel mit dem vorletzten Element und lässt diese wieder einsinken.
und so weiter. und so weiter.

Hoffe, das hilft ein wenig beim Verstehen.
Am besten mal aufzeichnen und nachvollziehen.

Gruß Woyzeck