Heap insert - Iteration 1

[Malou]

Hallo allerseits,

Ich weiss, dass ich mit meiner Frage/Bemerkung sehr spät komme, aber ich denke, dass es auch für die nächsten Klausuren helfen wird, dies zu klären.

Bei der Methode Heap Insert in Nabla wird die Induktionsbasis als Iteration gezählt. Das heisst, dass wir nur das Einfügen eines Keys als erste Iteration zählen sollten. Ich versteh jedoch nicht, warum erst in der zweiten Iteration der neue Element mit seinem Vorgänger mögl. vertauscht wird und nicht gleich in der ersten Iteration.
In dem Video (https://www.youtube.com/watch?v=j-r4YOPFp7E) wird zum Zeitpunkt 18:22 folgendes gesagt:

In jeder Iteration [muss] einfach den Wert des aktuellen Knotens mit dem Wert seines unmittelbaren Vorgängers vertauscht werden, falls letzterer grösser als ersterer ist.

Laut dieser Aussage sollte ja schon nach der ersten Iteration den Wert des eingefügten Key mit dem Wert seines unmittelbaren Vorgänger vertauscht werden, falls grösser. In Nabla ist es jedoch nicht der Fall...

Gibt es einen Grund für diese Diskrepanz?

LG

Malou

[Prof. Karsten Weihe]

Erst einmal eine schnelle Antwort für den 20.9.: Sollte es eine Nabla-Aufgabe geben, in der unklar sein könnte, was als erste Iteration zählt, dann wird das in einem zusätzlichen Hinweis spezifiziert. Sie müssen sich also nicht merken, bei welcher Aufgabe jetzt was am Anfang als Iteration zählt.

KW

[Malou]

Vielen Dank für die schnelle Antwort!

Das wird in der Klausur sehr hilfreich sein.

Malou