Heap Sort falsch! hier richtig :

[Megabit]

und zwar ist folgendes :

wenn man eine folge hat 2318752 , dann wird zuerst das erste hergenommen

2

dann das 2te
2 3
3 das wird versickert : 2
dann die 3te zahl:
3
2 1 ist bereits richtig
dann die 4te zahl:
3 3 8
2 1 wird wieder versickert 8 1 und nochmals 3 1
8 2 2
........

also nicht wie im Script geschrieben, alles nacheinander eintragen und dann mit n/2 SONDERN nach der reihe eintragen UND immer wieder versickern

Nachtrag: angeblich stimmt auch der im Skript, mir jetzt egal , so mach ich es ;)

[moose]

Original geschrieben von Megabit
und zwar ist folgendes :

wenn man eine folge hat 2318752


seite47, Heapsort(A), zeile 1: ErstelleHeap(a);

seite48, ErstelleHeap(a)
für 2318752 wird also so vorgegangen;

zuerst den baum zeilenweise anfüllen:
2
3 1
8 7 5 2

dann werden die knoten (n/2 bis 1) versickert bis n:
also zuerst knoten 3 (key=1)
2
3 5
8 7 1 2
dann knoten 2 (key=3)
2
8 5
3 7 1 2

dann knoten 1 (key=2)
8
2 5
3 7 1 2
zweier muss weiter versichkern
8
7 5
3 2 1 2


dann ist der heap fertig und kann sortiert werden
lg peter