Also nochmal das Grundprinzip von HeapSort.
Du hast ein Array gegeben, von dem du nicht ausgehen kannst, dass es richtig sortiert ist (wie ein heap). (1)
Noch ist es wichtig zu nennen: handelt es sich um einen "Min-Heap" oder "Max-Heap"?
Min-Heap: Wurzel ist kleinstes element.
Max-Heap: Wurzel ist größtes element.
Nächste wichtige info: Ist dies ein Binär, Trinär oder n-närer Heap?
(meist binär)
Wegen (1) musst du Heapify, auf jeden Knoten (angefangen bei dem letzten) aufrufen. Wenn
du ein Beispiel-Array als (binären Baum) aufzeichnest, merkst du schnell, dass die unterste "Zeile", also die Blätter unspektakulär sind, weil keine Kinder.
Heapify auf einen Knoten soll die HeapEigenschaft überprüfen, d.h. bei Min-Heap:
wähle kleinstes Kind und überprüfe, ob es kleiner ist, als aktueller Knoten, wenn ja -> Swap, wenn nein... nix machen und Heapify aufs nächste.
(Analog umgedrehte logik beim Max-Heap).
Fragen:
* Wieso startet dein "Heapify-Schleifen"-Index "i" bei knoten.length - 1 /2 ??... Muss man nicht einfach beim letzten Element anfangen?
* Was soll das "end" sein?
Wenn du das erklären kannst, können wir vielleicht in deine Implementierung durchblicken, ansonsten ein Tipp:
Schreibe dein Programm wirklich so, wie du es verstehst (bildlich). Ergo: Mach dir die Mühe und Schreibe eine Klasse "Heap" die jeden Wert ihres "Binären-Heap-Baumes" mit einem Index und einem eigentlichen Wert versieht. (dies ist auch ein sehr wichtiger Unterschied: Stelle eines Knotens und dessen Wert zu unterscheiden).
EDIT:
Den Algo, den ich oben beschrieben hab, war halt Thema an unserer Uni. Ich kann also nich garantieren, dass es bei euch auch so abläuft. (p.s. erläutere deinen Heapsort-algo vllt anhand von nem Beispiel??)
