Heap as Array - Array Positions

stef
Erstie
Erstie
Beiträge: 16
Registriert: 25. Sep 2012 14:59

Heap as Array - Array Positions

Beitrag von stef »

Hallo,

ich glaube ich stehe richtig auf dem Schlauch...

Ich bin mir zwar sicher, dass ich verstanden habe wie der Algorithmus funktioniert, aber ich verstehe nicht wie sich das Array TheHeap und das Array Positions füllt bzw. verändert.
Die Veränderung von dem Array TheHeap verstehe ich noch. Die Position wird mit dem Element getauscht, welches man auch in dem Baum tauschen würde um die Heapeigenschaft wieder herzustellen.
Aber die Änderungen im Positions-Array kann ich einfach nicht nachvollziehen... :(

Kann wir da jemand helfen?

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Heap as Array - Array Positions

Beitrag von JannikV »

Hey,

von welchem Algorithmus, also von welcher Methode sprichst du denn?
Du hast erstmal nur ganz allgemein Heap as Array genannt, aber nicht mit welcher Methode sich da etwas verändern soll und was daran noch unklar ist.

VG

stef
Erstie
Erstie
Beiträge: 16
Registriert: 25. Sep 2012 14:59

Re: Heap as Array - Array Positions

Beitrag von stef »

Also gehen wir vom Heap as array :Extract minimum aus...
Dann wird ja die Wurzel gelöscht bzw. mit dem letztem Wert überschrieben und anschließend wieder nach unten getauscht bis keine Verletzung des Heaps mehr vorhanden ist.

Dem entsprechend tauschen sich auch die Positionen in dem Array von TheHeap.
Was ich nicht verstehe ist das Array Positions. Ich kann dort die Reihenfolge der Vertauschung/Änderung nicht nachvollziehen... :( Vielleicht verstehe ich auch einfach nicht was das Array Positions macht ?
Dateianhänge
Unbenannt.JPG
Unbenannt.JPG (34.28 KiB) 272 mal betrachtet

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Heap as Array - Array Positions

Beitrag von JannikV »

Hm, das Array Positions beschreibt an welcher Position ein Element im Heap liegt.
Aber ohne konkretere Frage ist das schwer zu beantworten. Vielleicht mal ne Sprechstunde aufsuchen?

Aber wir können uns ja mal dein Bild angucken.
Ich denke dein Beispiel verletzt Implementationsinvariante 6.2.
Nehmen wir TheHeap[1]. Das dortige Element hat die ID 2. Das heißt in Positions[2] müsste 1 stehen. Aber da steht 3.

VG

stef
Erstie
Erstie
Beiträge: 16
Registriert: 25. Sep 2012 14:59

Re: Heap as Array - Array Positions

Beitrag von stef »

hmm, glaub dann werde ich mal eine Sprechstunde aufsuchen..trotzdem Danke für die Antwort. :)
Das Bild war aus den Folien..ist dann in den Folien ein Fehler?

Viele Grüße

Antworten

Zurück zu „Archiv“