wie habt ihr denn die aufgaben gelöst.
was muss man z.b bei der zusatz 3 machen? muss man da jetzt den baum malen und dann auflösen damit die kleinste zahl oben steht oder wird da das arry verlangt? wenn jemand zu den zusatz aufgaben weiter helfen kann wäre ich sehr dankbar. braucht die zusatz punkte damit ich 50% habe und komme leider nicht von alleine drauf.
Ich denke, du musst das Feld nach jedem Swap zeichnen. Dazu einfach die Anweisung befolgen: Das einzige störende Element ist das erste, da 27 zu groß ist (wir reden ja immer über MinHeaps).
Daraus ergibt sich, dass du im ersten Schritt die drei Zahlen 27-3-13 bearbeiten musst, was h[1], h[2*1] und h[2*1+1] entspricht.
Versuche einfach mal, den Algorithmus für siftDown(i) stur anzuwenden, dann müsste es schon klappen.
Ich hoffe, ich habe nicht an deinem Problem vorbei geredet
Zusatzaufgabe 1
Find ich persönlich ziemlich sch...lecht, bzw. aufwändig (glaub ich), ich hab doch keine Lust für alle 3 Sortieralgos Best/Worst-Case rauszusuchen. HeapSort braucht doch z.B. überhaupt keine Vergleiche - sofern der Heap besteht - und falls nicht - soll ich jetzt wirklich Grundmengen suchen wo Heapify best und worstcase erreichen oder wie? Quicksort... toll... Mergesort hab ich festgestellt, dass der best case sogar 4 schafft, worst case 5 (indem man den Algo Tupel mergen lässt die kreuzweise sind quasi, (2 5) (3 6) mergen z.B. ist "teuer"). Ein Algorithmus in 5 Vergleichen zum sortieren von 4 Zahlen finden müsstest du hinkriegen, ein bisschen knobel sollten reichen.
Zusatzaufgabe 2
Da allerdings bin ich selbst noch am Knobeln, ich fürchte das geht über simples sort5 und ein paar Swaps hinaus, aber keine Ahnung, leider.
Zusatzaufgabe 3
Wie schon geschrieben, im Buch auf seite 131 steht der Pseudocode für "siftDown()". Wenn du einen Binärbaum in Feldform hast, gilt, dass für das Element an i. Stelle, dass dessen linkes Kind bei 2i und sein rechtes Kind bei 2i+i ist, mit dem Vorwissen sollte das verständlich sein. Du schaust dir linkes und rechtes Kind vom Element an, nimmst das kleinere und vergleichst es mit dem Elternelement. Ist jenes größer, tauchst du die beiden und machst dann grad so weiter bis es passt.
338364: <Alanna> Saying that Java is nice because it works on all OS's is like saying that anal sex is nice because it works on all genders
Z2 geht, indem man sich einmal fünf Elemente mit sort5 sortieren lässt und dann für die restlichen drei mit binärer Suche jeweils die richtige Position sucht und dort einsetzt
