Algorithmen[6]#2

[elitoliker]

und was mache ich dann?
1568 wie kann ich es denn hinschreiben?. komme nicht weiter

1568
1658 ???
1586 ???

[salami]

Am besten zuerst die Bäume zeichnen, um besser zu sehen, welche Möglichkeiten es gibt.
Beachten:

• "Kinder" müssen immer größer oder gleich sein wie ihr Vater
• Jede Ebene, außer die ganz unten, muss vollständig aufgefüllt sein
• Die unterste Ebene muss von links nach rechts aufgefüllt werden

Wenn du die Bäume hast, machst du ein Array mit so vielen Feldern wie Elementen im Baum und schreibst sie nacheinander rein.
In Feld 0 steht das Element ganz oben, in 1 das in der 2. Ebene links, in 2 das in der 2. Ebene rechts, in 3 das in der 3. Ebene links usw...

[elitoliker]

ja und somit sind meine lösungen richtig oder?
habe die bäume gemacht und das mit den eltern und kindern durchgemacht. geht für die 2 fälle.

jedoch bin ich mir nicht sicher wie man die letzte zahl vergleichen kann. da bei eltern (2 eintrag) die kinder bei 4 und 5 sind.

somit kann ich nur die erste zahl auf ihre kinder vergleichen und zuletzt nur das eine linke kind von der zweiten zahl. oder liege ich da falsch?

[salami]

Ja deine drei Lösungen scheinen zu stimmen.

Statt zu kontrollieren, ob die Kinder größer sind, kannst du auch einfach bei jedem Knoten kontrollieren, ob der Vater(bzw. die Mutter ) kleiner ist.
Also ob das Element in der Ebene darüber, mit dem es verbunden ist, kleiner ist. Wenn das bei allen Knoten passt, dann stimmt es. Die Wurzel hat natürlich keinen Vater, da sie ja das kleinste Element ist.

Das ist aber nur bei MinHeaps so. bei MaxHeaps ist es genau umgekehrt, da müsste der Vater immer größer sein.