SS14 A5 Haldensortierung: als nächstes betrachtetes Element

Bachelor Algorithmen und Datenstrukturen
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

SS14 A5 Haldensortierung: als nächstes betrachtetes Element
Hallo,

gegeben ist ein Feld mit den Werten 6703152, dessen fetter Bereich bereits die Max-Heap Eigenschaft erfüllt.

Zudem ist noch folgende Klasse gegeben:

class ComparatorAscByFieldT implements Comparator<W> {
    @Override
    public int compare (W o1, W o2) {...
}

jetzt soll man die Element des Feldes angeben, die das Verfahren im “Versickerschritt” für das nächste Element mit Hilde des ComparatorAscByFieldT vergleicht.

Das wäre mein Gedankengang:

  1. Die fetten Elemente sind bereits in der Form eines max-Heaps, als nächstes sehe ich mir also das Element 0 an.
  2. Die Kinder von 0 sind 5 und 2, deswegen vergleiche ich 5 und 2
  3. Ich tausche 0 mit dem größeren der beiden Kinderelement (5)

Also würde ich die Elemente 0, 5 und 2 ankreuzen. Der FSI-Lösungsvorschlag gibt aber 2, 5 und 6 an.
Warum ist das so?

https://fsi.cs.fau.de/dw/pruefungen/bachelor/aud/loesungss14

Liebe Grüße
Speedy

3

Hi,

I think what “2,5 and 6” on FSI-Lösungsvorschlag is the indices of the array.
So your answer is correct because index[2] = 0, index[5] = 5, and index[6] = 2.

I hope it helps.

2 „Gefällt mir“
4

Oh, that was stupid of me :scared:
Thanks for pointing this out.