Heapsort erklären?

[AlexII]

Hallo,

ich versuche schon seit einer Zeit den Heapsort zu verstehen, aber es geht mir nicht in den Kopf.
Ich hab hier dieses Video gefunden, das ist zwar laut Kommentaren gut, aber ich verstehe nicht wieso ab der 55 Sekunde die 2 mit der 4 nicht vertauscht wird? Kann mir das jemand erklären? Danke!

http://www.youtube.com/watch?v=a7aXY...eature=related

[Romiox]

Wenn ich das richtig sehe werden bei 1:18 genau diese beiden Zahlen vertauscht *scratch*

[AlexII]

Tatsächlich!

Ja ich hab da Pause geklickt, weil wozu weiterschauen, wenn man das eine nicht verstanden hat.

Danke dir!

[Luckie]

War es bei Heapsort nicht so, dass man es beim ersten Schritt in zwei Teile teilt und dann von den beiden Teilen jeweils, falls nötig das erste und letzte Element vertauscht? Dann teilt man die Teile wieder und vertauscht bei Bedarf wieder. Und das geht so lange bis man nicht mehr teilen kann?

[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

[Luckie]

Und was habe ich jetzt erklärt?

[Woyzeck]

Zitat von Luckie:

Und was habe ich jetzt erklärt?

Bin mir nicht ganz sicher, was dein beschriebener Algorithmus macht.

Jedenfalls habe ich das Video gerade mal grob geschaut und es deckt sich mit meiner Beschreibung.

[Luckie]

Oder war das Selectionsort, was ich beschrieben habe?

[Woyzeck]

Zitat von Luckie:

Oder war das Selectionsort, was ich beschrieben habe?

ne, bei selectionsort wird nicht geteilt. Dort sucht man sich ja immer das größte bzw. kleinste Element und fügt es an Anfang bzw. Ende des unsortierten Teils der Liste.

Teilen des Feldes erinnert mich an Quicksort oder Mergesort.