| Die letzten 2 Beiträge |
| 3FingerbreitNougat |
RE: Heap
| Zitat: |
Original von Algo
1. An welchen Positionen könnte das drittgrößte Element bei einem Heap mit 7 Elementen stehen?
|
Das drittgrößte Element steht entweder in Ebene 1 oder Ebene 2. Dabei ist Ebene 0 der "Head" des Heaps.
Die Positionen könnten also H[3], H[4], H[5], H[6], H[7] sein, wobei H[x] das x-te Element in der Halde ist. Der Head hat den x-Wert 1.
| Zitat: |
Original von Algo
2. Wie viele Elemente in einem Heap mit 30 Positionen sind mindestens kleiner als das Element an der Position 8?
|
Ab diesem Element (8) sind alle folgenden Elemente kleiner als es selbst, d.h. du brauchst eigentlich nur die Anzahl der Elemente nach dem 8ten Element.
Tipps hier ganz klein:
Tipp: Du hast hier einen Teilbaum.
Tipp2: Wieviele Elemente fallen weg wenn du einen Teilbaum löschst?
Tipp3: Solange Teilbäume löschen bis du bei Element 8 als Head bist.
MfG  |
| Algo |
Heap
In meinen Übungsklausuren, gibt es immer eine Frage zum Heap wie beispielsweise:
1. An welchen Positionen könnte das drittgrößte Element bei einem Heap mit 7 Elementen stehen?
2. Wie viele Elemente in einem Heap mit 30 Positionen sind mindestens kleiner als das Element an der Position 8?
Einen normalen Heap kann ich sortieren, aber hier weiß ich nicht wie ich vorgehen soll.
Heap aufzeichnen bei 30 Positionen geht ja auch nicht wirklich, bzw. gibt auch eine Frage da sind es 60 Positionen.
Wie gehe ich bei dieser Fragestellung am Besten vor? |
|
|
