kleinstes Element im max-heap < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 03:14 Fr 18.11.2011 | | Autor: | Sin777 |
| Aufgabe | Gegeben sei eine Implementierung eines Heaps mit den Operationen Insert und ExtractMax. Hierbei
fügt Insert ein Element in den Heap ein, und ExtractMax entfernt das größte Element aus dem Heap
(und stellt die Heapbedingung wieder her). Wie können Sie diese Implementierung nutzen, wenn
Sie eigentlich eine Funktion brauchen, die das Minimum der Elemente im Heap zurückgibt? |
Die Aufgabe gibt gerade mal einen Punkt aber ich komme einfac nicht drauf. Ich mache mri schon den ganzen Tag skizzen aber weiß nicht, wie man das geschickt lösen kann.
Kann mir jemand helfen?
Gruß
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:11 Fr 18.11.2011 | | Autor: | felixf |
Moin!
> Gegeben sei eine Implementierung eines Heaps mit den
> Operationen Insert und ExtractMax. Hierbei
> fügt Insert ein Element in den Heap ein, und ExtractMax
> entfernt das größte Element aus dem Heap
> (und stellt die Heapbedingung wieder her). Wie können Sie
> diese Implementierung nutzen, wenn
> Sie eigentlich eine Funktion brauchen, die das Minimum der
> Elemente im Heap zurückgibt?
>
> Die Aufgabe gibt gerade mal einen Punkt aber ich komme
> einfac nicht drauf. Ich mache mri schon den ganzen Tag
> skizzen aber weiß nicht, wie man das geschickt lösen
> kann.
Ich finde die Aufgabe nicht so toll gestellt. Ist gemeint, dass man immer nur das Minimum haben will (und nie das Maximum), und diese Implementierung nutzen will? In dem Fall reicht es voellig aus, anstelle dem Wert $x$ den Wert $-x$ in den Heap zu packen und beim Herausnehmen das Vorzeichen wieder zu wechseln. Schliesslich ist $-x > -y$, wenn $x < y$ ist.
Falls man aber sowohl mal kleinste wie auch groesste Elemente haben will, kann man da nicht viel machen, denke ich, ausser den Heap doppelt zu speichern, wobei man einmal die Elemente $x$ direkt einfuegt und ein anderes Mal jeweils $-x$. Dann kann man zum Schluss die kleinsten und groessten Elemente schnell herauslesen.
Ich vermute aber eher, das ersteres gemeint ist (sprich: man will nur die kleinsten Werte herausnehmen).
LG Felix
|
|
|
|
