Heap |
| 12.06.2010, 08:09 | Auf diesen Beitrag antworten » | ||||
| 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? |
||||
|
|
|||||
| 12.07.2010, 01:36 | Auf diesen Beitrag antworten » | ||||
| 3FingerbreitNougat | RE: Heap
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.
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  |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
