GIN2 SS05 Lösung A21

Prof. Dr. W. Conen

(auf Bitte von M. Schwerthoff)

A21, Entscheidungsbaum für die Vergleiche bei einem Top-Down-Heapsort Array-basierter Top-Down-Heapsort (wie in A8), aufsteigend, zu

verwendende Vergleiche: ¸ Beginn unter Berücksichtigung der üblichen Vorgehensweise: hintere

Hälfte uninteressant Heap vergleicht zuerst die Söhne

Probieren sie das auch für Bottom-Up! (nicht, dass es da viele Unterschiede gäbe bei einer 3er-Sequenz, bei 4er schon) Bei Bottom-Up können sie (wie beim Zählen der Vergleiche bei Aufgabe 9

angewendet), davon ausgehen, dass es, wenn sie beim Suchen nach dem Einfügepunkt wieder bis zur Wurzel hochwandern müssen (der Schlüssel also dort bleiben kann, wo er ist, weil er der größte Wert ist), „oben“ keinen Vergleich mehr zwischen dem Schlüssel und sich selbst gibt, sondern der Heapsort anhand eines Indexvergleichs merkt: Moment, ich bin wieder am Ausgangspunkt (uns interessieren ja nur die Schlüsselvergleiche und nicht anderer Aufwand, der aus dem Management der Datenstruktur entsteht.

A21, Entscheidungsbaum für die Vergleiche bei einem Top-Down-Heapsort a2:a3

a1:a3 a1:a2

a3:a1 a3:a2a1:a2 a3:a2

a1,a2,a3 a2,a1,a3 a3,a2,a1 a2,a3,a1 a3,a1,a2 a1,a3,a2 a3,a2,a1 a2,a3,a1

Nein Ja

Nein NeinJa

Ja Ja Ja JaNeinNeinNeinNein

Nicht erreichbar!Heapsort führt diesenVergleich aber (unnötigerweise) aus! [a2<a3 Æ a3<a2 – Widerspruch!]

unnötig,aber ok[a2=a3]

Um den Baum aufzubauen, kann es sinnvoll sein, den Zustand des Arrays an die Knoten zu schreiben (obenan einigen Beispielen demonstriert, KT steht für „kein Tausch“, T für Tausch, 2. Ph. für „zweite Phase“ ) – dasmüssen sie aber nicht machen, der „nackte“ Baum reicht aus als Lösung.

KT: a1,a2,a32. Ph.: a3,a2|a1

T: a3,a2,a12. Ph.: a1,a2|a3

T: a2,a1|a3 KT KTT: a2,a3|a1 KT KTT: a1,a3|a2 T: a2,a3|a1

T: a2,a1,a32.Ph.: a3,a1|a2

KT: a1,a2,a32.Ph.: a3,a2|a1

Ja