Heapeigenschaft erstellen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:02 Fr 03.12.2010 | | Autor: | pyw |
| Aufgabe | | Warum kann man einen Min-Heap aus einem Array mit n Elementen in O(n) erstellen? |
Hi,
leider finde ich sonst nirgends eine ordentliche Erklärung dafür. Bei mir wird in einer Übungsaufgabe nur darauf verwiesen, dass dies ja in einer Vorlesung gezeigt wurde, in der ich aber nicht da war (und auch sonst keiner wirklich was davon weiß =O).
Hier ist eine Beschreibung, wie man den Heap erstellt:
Um ein Array in einen Heap zu überführen, beginnt man in der Mitte des Arrays. Man „versickert“ nun sukzessiv alle davor liegenden Knoten, bis das erste Element versickert wurde. Versickern heißt, dass man einen Knoten mit dem größeren seiner beiden Nachfolgeknoten vertauscht, falls dieser größer ist als er selbst, und damit so lange fortfährt, bis er keinen Nachfolgeknoten mehr hat, der größer ist als er selbst.
Die Nachfolger eines Knotens mit dem Index i liegen an den Positionen 2·i und 2·i+1.
M. E. ist dies nur in O(n log n) möglich, da es im schlechtesten Fall passieren kann, dass jedes Element bis ganz nach unten durchsickert. Wo ist mein Denkfehler?
Wäre über schnelle Hilfe heute sehr dankbar :)
Freundliche Grüße,
pyw
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:39 Fr 03.12.2010 | | Autor: | felixf |
Moin pyw,
> Warum kann man einen Min-Heap aus einem Array mit n
> Elementen in O(n) erstellen?
>
> leider finde ich sonst nirgends eine ordentliche Erklärung
> dafür. Bei mir wird in einer Übungsaufgabe nur darauf
> verwiesen, dass dies ja in einer Vorlesung gezeigt wurde,
> in der ich aber nicht da war (und auch sonst keiner
> wirklich was davon weiß =O).
>
> Hier ist eine Beschreibung, wie man den Heap erstellt:
> Um ein Array in einen Heap zu überführen, beginnt man in
> der Mitte des Arrays. Man „versickert“ nun sukzessiv
> alle davor liegenden Knoten, bis das erste Element
> versickert wurde. Versickern heißt, dass man einen Knoten
> mit dem größeren seiner beiden Nachfolgeknoten
> vertauscht, falls dieser größer ist als er selbst, und
> damit so lange fortfährt, bis er keinen Nachfolgeknoten
> mehr hat, der größer ist als er selbst.
> Die Nachfolger eines Knotens mit dem Index i liegen an den
> Positionen 2·i und 2·i+1.
>
> M. E. ist dies nur in O(n log n) möglich, da es im
> schlechtesten Fall passieren kann, dass jedes Element bis
> ganz nach unten durchsickert. Wo ist mein Denkfehler?
> Wäre über schnelle Hilfe heute sehr dankbar :)
eine Begruendung, warum man tatsaechlich $O(n)$ bekommt, findest du ![[]](/images/popup.gif) hier.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:03 Fr 03.12.2010 | | Autor: | pyw |
Ärgerlich, dass ich den Artikel nicht selbst gefunden habe :[
Aber trotzdem danke, Verständnislücke geschlossen 
|
|
|
|
