Heap insert - Iteration 1

Bei Postings zu Algorithmus X lassen Sie Ihren Betreff bitte mit
"X: " beginnen, bei allgemeinen Postings zu Nabla bitte mit "Nabla: ", jeweils gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Algorithmus X lassen Sie Ihren Betreff bitte mit
"X: " beginnen, bei allgemeinen Postings zu Nabla bitte mit "Nabla: ", jeweils gefolgt von einer möglichst präzisen Überschrift, danke!
Benutzeravatar
Malou
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 19. Jun 2016 17:54

Heap insert - Iteration 1

Beitrag von Malou » 19. Sep 2016 12:03

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. :lol:

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
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Heap insert - Iteration 1

Beitrag von Prof. Karsten Weihe » 19. Sep 2016 12:53

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

Benutzeravatar
Malou
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 19. Jun 2016 17:54

Re: Heap insert - Iteration 1

Beitrag von Malou » 19. Sep 2016 13:02

Vielen Dank für die schnelle Antwort!

Das wird in der Klausur sehr hilfreich sein.

Malou

Antworten

Zurück zu „AuD: Arbeit mit Nabla“