Frage zu Heapsort

[Senior Sanchez]

Hallo,

Also irgendwie habe ich gerade einen Paul. Wir sollen einen (Min-)Heapsort implementieren und als Test dazu die folgende Zahlenfolge sortieren: 8, 3, 7, 1, 5, 9, 6.

Als erstes lasse ich einen Heap konstruieren (habe ich über ein Einfügen am Anfang und ein durchsickern realisiert): 1 5 3 6 9 7 8
Das ist meiner Ansicht nach ein gültiger Heap, die Heapbedingung (jedes Parent ist kleiner als seine beiden Kinder) ist erfüllt.

Nun geht es los. Das erste Element kann ich direkt entfernen, denn es ist das kleinste. So bleibt 5 3 6 9 7 8. Nun sieht es Heapsort vor, das erste und letzte Element miteinander zu vertauschen und das erste Element dann wiederum durchsickern zu lassen.
5 3 6 9 7 8 --> vertauschen 8 3 6 9 7 5 --> durchsickern lassen 3 7 6 9 8 5

Aber dies ist kein korrekter Heap! 6 ist größer als sein Kind 5, aber trotzdem taucht 6 weiter oben im Heap auf.

Wo liegt mein Fehler?

[Sephiroth]

Inf 3 ist ne Weile her, aber ich glaube dein Anfangsheap ist schon nicht korrekt. ich komm auf 1 3 6 8 5 9 7.
Dann die 1 entfernt, 3 mit 7 vertauscht und heapify auf das neue erste Element (die 7) ergibt dann 3 5 6 7 9 8.
3 entfernt, 5 mit 8 getauscht und heapify auf 8 ergibt 5 6 7 9 8.

...

edit:
achja, jetzt seh ich wo bei dir der fehler lag: du musst die 6 noch mit der 5 vertauschen (versickern)

[Senior Sanchez]

Inf 3 ist ne Weile her, aber ich glaube dein Anfangsheap ist schon nicht korrekt. ich komm auf 1 3 6 8 5 9 7.
Dann die 1 entfernt, 3 mit 7 vertauscht und heapify auf das neue erste Element (die 7) ergibt dann 3 5 6 7 9 8.
3 entfernt, 5 mit 8 getauscht und heapify auf 8 ergibt 5 6 7 9 8.

...

edit:
achja, jetzt seh ich wo bei dir der fehler lag: du musst die 6 noch mit der 5 vertauschen (versickern)

Nope, leider alles nicht richtig ;)
Ich habe den Fehler dank eines Kommilitonen gefunden. Mein Heap ist auf jeden Fall korrekt gewesen, am Anfang, die Heap-Bedingung ist auch erfüllt.

Der Fehler liegt im Vertauschen. Ich darf nicht das erste Element entfernen und dann das neue erste Element mit dem letzten vertauschen, sondern ich muss sofort, als ohne es zu entfernen, das erste Element mit dem letzten vertauschen. Alternativ kann man aber wirklich das erste Element sofort entfernen, muss dann aber das letzte Element an die erste Stelle verschieben.

So haut es hin.

[Sephiroth]

achja, so war das ... wie peinlich :usad:

prinzipiell geht die methode (von mir) aber auch ... ist dann nur kein heapsort mehr X-D

[Gast]

Alternativ kann man aber wirklich das erste Element sofort entfernen, muss dann aber das letzte Element an die erste Stelle verschieben.



so funktioniert heapsort normalerweise auch.

das erste element wird mit dem letzten vertauscht und das ehemals letzte (nun erste) element wird versickert und damit der heap H(i,j-1) neu aufgebaut.

das ganze wird so lange rekursiv gemacht bis nur mehr der Heap H(1,1) besteht, dann ist das array sortiert.

[Senior Sanchez]

so funktioniert heapsort normalerweise auch.

das erste element wird mit dem letzten vertauscht und das ehemals letzte (nun erste) element wird versickert und damit der heap H(i,j-1) neu aufgebaut.

das ganze wird so lange rekursiv gemacht bis nur mehr der Heap H(1,1) besteht, dann ist das array sortiert.

Ich weiß ;)
Somit gewährleistet man eine in-place Sortierung.

So habe ich das jetzt auch implementiert, auch wenn ich bei dem Min-Heap somit eine absteigende Sortierung erreiche.