Heap < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Zeigen sie die folgende Aussage:
1.) Ein Heap mit n Elementen hat die Höhe [mm] $\lfloor log(n)\rfloor$.
[/mm]
2.) Ein Heap mit n Elementen hat höchstens [mm] $\lceil \frac{n}{2^{h+1}} \rceil$ [/mm] viele Knoten der Höhe h. |
Hi Leute!
Ich hab mir zu Teilaufgabe eins schon Gedanken gemacht komme aber nun an einer bestimmten Stelle nicht mehr weiter:
n = Elementanzahl
k = Zeilenanzahl
[mm] $\overbrace{2^{k-1}-1}^{\text{Anzahl Elemente eine Zeile vorher}} [/mm] < n [mm] \leq \overbrace{2^k-1}^{\text{Anzahl Elemente bei vollen Zeilen}}$
[/mm]
[mm] $\Leftrightarrow 2^{k-1} \leq [/mm] n [mm] \leq 2^k-1$
[/mm]
[mm] $\Leftrightarrow 2^k{-1} \leq [/mm] n < [mm] 2^k$
[/mm]
[mm] $\Leftrightarrow [/mm] k-1 [mm] \leq \lfloor log(n)\rfloor [/mm] < k$
Wie komme ich hier nun weiter, damit ich zeigen kann, dass Teilaufgabe 1 immer gilt?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:24 Sa 20.04.2013 | | Autor: | bandchef |
Hi Leute!
Sorry, wenn ich den Thread hier nun pushe, aber ich würde mich sehr freuen, wenn man mir helfen könnte!
|
|
|
| |
|
Hallo,
es ist doch kaum ein Jahr her ...
Bist du so vergesslich? 
https://matheraum.de/forum/Hoehe_eines_Heaps/t884420
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:13 Sa 20.04.2013 | | Autor: | bandchef |
Nein. Ich wusste natürlich noch, dass ich diese Aufgabe schon mal gestellt hatte. Ich bin aber nun da wieder drüber gestolpert. Ich hab mir sogar diese Thread nochmal durchgelesen und dann beim gleichen Problem wieder hängen geblieben, zumal im alten Thread die letzte Frage unbeantwortet geblieben ist.
Zustäzlich hab ich in diesem Thread noch eine zweite Teilaufgabe hinzugefügt...
|
|
|
| |
|
Wenn ich nun also als "Fastergebnis" diese Zeile hier hab $ [mm] \Leftrightarrow [/mm] k-1 [mm] \leq \lfloor log(n)\rfloor [/mm] < k $ was muss ich hier dann noch weiter machen, um endlich zum Beweis zu kommen, dass die Höhe eines Heaps mit n-Elementen IMMER [mm] $\lfloor log(n)\rfloor$ [/mm] hat?
Edit: Ahhhh! Jetzt glaub ich hab ich's kapiert!
$ [mm] \Leftrightarrow [/mm] k-1 [mm] \leq \underbrace{\lfloor log(n)\rfloor < k}_{\text{Da ganze Zahlen, gilt: }\lfloor log(n)\rfloor = k-1} [/mm] $
Durch diese Gaußklammern kann das "<"-Zeichen durch "=" ersetzt werden.
Wenn ich nun in meinem Heap 3 Elemente habe, hab ich zwei Zeilen. So gilt dann nun: [mm] $\lfloor log(3)\rfloor [/mm] = 2-1$, was richtig ist. Demzufolge beginnt die Zählung der Höhe bei h=0.
Stimmt das so?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:20 Mo 22.04.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
Ich hab mir nun zur zweiten Teilaufgabe noch Gedanken gemacht. Mit dem Zusammenhang, dass gilt: [mm] $h=log_2(n)$
[/mm]
[mm] $\lceil \frac{n}{2^{h+1}} \rceil [/mm] = [mm] \lceil \frac{n}{2^{log_2(n)+1}} \rceil [/mm] = [mm] \lceil \frac12 \rceil [/mm] = 1$
Aber ehrlich gesagt weiß ich jetzt nich so recht, was ich da jetzt berechnet haben soll!
Kann mir das jemand sagen, bzw. korrigieren, wenn es nicht stimmt?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:20 Mo 22.04.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:20 Mo 22.04.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
