Un pò di dubbi sulle Heap
Ho una serie di problemi nello studio delle heap.
Per esempio l' equazione di ricorrenza per Max-heapify è:
[tex]T(k)=T(2k/3)+\theta(1)[/tex]
Questo perchè se prendo un sottoalbero di dimensione n, e poi considero i sottoalberi radicati nei figli ognuno di essi non può avere dimensione maggiore di 2n/3, ma come si dimostra?
Non ricordo più le proprietà degli alberi, leggo che il numero massimo di nodi ad altezza h è [tex]2^{h+1}-1[/tex] ma non mi quadra...se disegno un albero binario completo con 7 nodi, e quindi di altezza due avrei [tex]2^{3}-1[/tex] che fa 7, ma io ho solo 4 nodi ad altezza h.......
E poi da qui come si arriva al fatto che il numero di nodi ad altezza h si può indicare come [tex]\frac{n}{2^{h+1}}[/tex] ?
Nel calcolo della complessità della costruzione di una maxheap ho questi calcoli:
[tex]\sum \left \lceil \frac{n}{2^{h+1}} \right \rceil O(h)[/tex] che diventa:
[tex]O(n\sum\frac{h}{2^h})[/tex]
L' unica cosa che non mi spiego è perchè dopo avere tolto il ceiling al denominatore non ho più [tex]2^{h+1}[/tex] ?
Per esempio l' equazione di ricorrenza per Max-heapify è:
[tex]T(k)=T(2k/3)+\theta(1)[/tex]
Questo perchè se prendo un sottoalbero di dimensione n, e poi considero i sottoalberi radicati nei figli ognuno di essi non può avere dimensione maggiore di 2n/3, ma come si dimostra?
Non ricordo più le proprietà degli alberi, leggo che il numero massimo di nodi ad altezza h è [tex]2^{h+1}-1[/tex] ma non mi quadra...se disegno un albero binario completo con 7 nodi, e quindi di altezza due avrei [tex]2^{3}-1[/tex] che fa 7, ma io ho solo 4 nodi ad altezza h.......
E poi da qui come si arriva al fatto che il numero di nodi ad altezza h si può indicare come [tex]\frac{n}{2^{h+1}}[/tex] ?
Nel calcolo della complessità della costruzione di una maxheap ho questi calcoli:
[tex]\sum \left \lceil \frac{n}{2^{h+1}} \right \rceil O(h)[/tex] che diventa:
[tex]O(n\sum\frac{h}{2^h})[/tex]
L' unica cosa che non mi spiego è perchè dopo avere tolto il ceiling al denominatore non ho più [tex]2^{h+1}[/tex] ?
Risposte
"ham_burst":
[quote="Darèios89"]Scusa, non ti seguo e mi sono dovuto fermare subito, non abbiamo mai detto che il numero di nodi interni è al massimo [tex]2^{h-1}-1[/tex], ma è [tex]2^h-1[/tex].
è la stessa cosa, ma indicati in modi diversi.
[tex]2^h-1[/tex] è il livello $h$ generico.
[tex]2^{h-1}-1[/tex] è la massima profondità che è valida la terminologia di "nodo interno".
se vuoi metterla così:
[tex]2^h-1[/tex] = [tex]2^i-1[/tex]
[tex]2^{h}-1[/tex] è $i=h-1$ con $h= log_2(n)$
foglie: $2^(log_2(n))$
nodi interni: $2^{log_2(n)-1}-1$
ok?[/quote]
Qui...se sostituiamo ad i quello che avevi scritto prima non funzionava credo, però se consideriamo k=0 l' uguaglianza vale, giusto? In una dimostrazione della pagina prima, in cui abbiamo(hai
) dimostrato il numero di nodi massimi ad altezza h usiamo [tex]2^{h-1}-1[/tex] cioè consideriamo i=h-1 con k=1, perchè? E' come se escludessimo l' ultimo livello delle foglie......ma i nodi interni non li calcoliamo a partire dalle foglie?EDIT: Sto leggendo che questa proprietà vale proprio fino ad h-1, quindi per questo al posto di i mettiamo h-1, giusto?
Dovrebbe quadrare.
"Darèios89":
Qui...se sostituiamo ad i quello che avevi scritto prima non funzionava credo, però se consideriamo k=0 l' uguaglianza vale, giusto? In una dimostrazione della pagina prima, in cui abbiamo(hai
esatto $h$ è da intendere come $i$ e da sostituire con $h-k$ con $k=1$.
ma i nodi interni non li calcoliamo a partire dalle foglie?
EDIT: Sto leggendo che questa proprietà vale proprio fino ad h-1, quindi per questo al posto di i mettiamo h-1, giusto?
Dovrebbe quadrare.
qua mi fai venire un dubbione. Per la validità si è fino ad h-1.
Appena torno a casa mi riprendo in mano il libro, ti saprò dire
EDIT:
ho ripensato a ciò, penso di aver scritto una cosa scorretta per dirne un'altra di altro significato.
Quando un po' di tempo cerco di correggere il post. Prendi per buoni la dimostrazione per induzione nell'ultimo post, che quello prende semplicemente la proprietà dell'heap e nulla di più.
Allora ho ricontrollato, e corretto i vari "errori" o manomissioni e sviste.
i nodi interni totali (come scritto nei post corretti) si calcola con: $2^h-1$ con $h$ calcolato a seconda del tipo di albero.
E' banale che sia vero, lo avevo pure scritto, ma per via di:
$2^{h-1}-1$ deriva da una mia idea di cercare di spiegare perchè i nodi interni totali di un albero completo sono $\lfloor n/2 \rfloor$ vedi i post precedenti.
ho preso come buona una mia idea (non dimostrata formalmente, ma abbozzata).
Anzi dimmi perchè è $2^h-1$ e non 1000*pippo? Così vedo se hai capito.
Se noti altre cose che non comprendi dimmelo, così correggo
i nodi interni totali (come scritto nei post corretti) si calcola con: $2^h-1$ con $h$ calcolato a seconda del tipo di albero.
E' banale che sia vero, lo avevo pure scritto, ma per via di:
$2^{h-1}-1$ deriva da una mia idea di cercare di spiegare perchè i nodi interni totali di un albero completo sono $\lfloor n/2 \rfloor$ vedi i post precedenti.
ho preso come buona una mia idea (non dimostrata formalmente, ma abbozzata).
Anzi dimmi perchè è $2^h-1$ e non 1000*pippo? Così vedo se hai capito.
Se noti altre cose che non comprendi dimmelo, così correggo
SI, devo leggerla meglio ma....funziona, o Dio non credo che il mio prof sarà così puntiglioso, basta che inizierò a dimostrare le heap e gli andrà bene, semmai mi interromperà se sbaglio qualche proprietà. Ho visto che hai modificato anche la dimostrazione, sei un angelo 
. Ora è un pò tardi, la leggo ma credo la capirò domani.
Per quanto riguarda il perchè i nodi interni sono [tex]2^{h}-1[/tex] credo perchè essendo un albero binario, abbiamo che il numero di nodi massimo (foglie) per ogni livello è una potenza di due, per questo se io considero 2^h ho le foglie, e se tolgo 1 ho esattamente la somma di tutte le foglie ai vari livelli......per questo ottengo i nodi interni.
Non saprei dire di meglio....un' improvvisata...
P.S Sempre nella dimostrazione mi manca una cosa, noi (tu ) abbiamo provato che la proprietà è vera per i=0 e lo abbiamo sostituito, subito dopo dici ipotesi: vera per i-1, la proviamo per il successivo cioè i, perchè? Cioè noi l' abbiamo verificata per i=0, non per i-1 o sbaglio? Forse perchè essendo il caso base i=0, è lo stesso che otteniamo mettendo [tex]i-1[/tex], perchè abbiamo i-1+1 e quindi rimane i, che era zero per ipotesi, così possiamo supporre di provarlo per il successivo di [tex]i-1[/tex] che è i? Non so se sono stato chiaro.
. Ora è un pò tardi, la leggo ma credo la capirò domani.Per quanto riguarda il perchè i nodi interni sono [tex]2^{h}-1[/tex] credo perchè essendo un albero binario, abbiamo che il numero di nodi massimo (foglie) per ogni livello è una potenza di due, per questo se io considero 2^h ho le foglie, e se tolgo 1 ho esattamente la somma di tutte le foglie ai vari livelli......per questo ottengo i nodi interni.
Non saprei dire di meglio....un' improvvisata...
P.S Sempre nella dimostrazione mi manca una cosa, noi (tu
) abbiamo provato che la proprietà è vera per i=0 e lo abbiamo sostituito, subito dopo dici ipotesi: vera per i-1, la proviamo per il successivo cioè i, perchè? Cioè noi l' abbiamo verificata per i=0, non per i-1 o sbaglio? Forse perchè essendo il caso base i=0, è lo stesso che otteniamo mettendo [tex]i-1[/tex], perchè abbiamo i-1+1 e quindi rimane i, che era zero per ipotesi, così possiamo supporre di provarlo per il successivo di [tex]i-1[/tex] che è i? Non so se sono stato chiaro.
"Darèios89":
Per quanto riguarda il perchè i nodi interni sono [tex]2^{h}-1[/tex] credo perchè essendo un albero binario, abbiamo che il numero di nodi massimo (foglie) per ogni livello è una potenza di due,
ok, ma Nì.
per questo se io considero 2^h ho le foglie, e se tolgo 1 ho esattamente la somma di tutte le foglie ai vari livelli......per questo ottengo i nodi interni.
No.
Quello che dici è una formulazione ricavata dalla "formula". Io chiedo da dove esce.
E' giusto che parli di "livelli" perchè è una somma dei nodi dei vari livelli...perciò?
P.S Sempre nella dimostrazione mi manca una cosa, noi (tu
no fai confusione, tra caso base ed ipotesi induttiva.
io ho dimostrato che è vera il caso base $i=0$, rileggi bene è un altezza rovesciata (se vuoi mettere è come parlando di $h-k$ con $k=0,....,h$ stesso discorso ma altro riferimento, ok?)
ora ipotizzo che è vera per $i-1$ cioè per un sottoalbero radicato (rileggi i post successivi).
poi faccio un passo induttivo e cerco di dimostrarlo per $i$. E' contorto, me ne rendo conto, ma mi baso semplicemente sulla definizione di sottoalbero e faccio un'induzione sull'albero (qualcosa di un pizzico più complicato di un'induzione normale, dimostro una Proprietà per induzione).
Ah va bene, ok, per quanto riguarda sempre i nodi interni, non so, lo sai che sono una frana a dimostrare 
. Ora non so l' unica cosa che mi viene, e che forse la ricavo sempre erroneamente dalla formula è questa. I nodi interni per definizione sono quei nodi che hanno uno o più figli, quindi se voglio determinare il numeri di nodi interni ad altezza h devo considerare tutti i nodi che hanno dei figli fino ad altezza h esclusa perchè la considero come livello delle foglie. Allora significa andare a sommare tutti i nodi ai vari livelli, cioè:
[tex]2^0+2^1+2^2+.....+2^n[/tex]
E quindi in quel modo se prendo in considerazione i=2 ottengo esattamente 7 nodi, se prendo i=1 ne ottengo 1. Sto pensando di scrivere altro ma temo di dire sciocchezze, non saprei se devo usare vista quella somma che ho scritto la serie geometrica.....ma già sto dimostrando per assurdo sicuramente
. Ora non so l' unica cosa che mi viene, e che forse la ricavo sempre erroneamente dalla formula è questa. I nodi interni per definizione sono quei nodi che hanno uno o più figli, quindi se voglio determinare il numeri di nodi interni ad altezza h devo considerare tutti i nodi che hanno dei figli fino ad altezza h esclusa perchè la considero come livello delle foglie. Allora significa andare a sommare tutti i nodi ai vari livelli, cioè:[tex]2^0+2^1+2^2+.....+2^n[/tex]
E quindi in quel modo se prendo in considerazione i=2 ottengo esattamente 7 nodi, se prendo i=1 ne ottengo 1. Sto pensando di scrivere altro ma temo di dire sciocchezze, non saprei se devo usare vista quella somma che ho scritto la serie geometrica.....ma già sto dimostrando per assurdo sicuramente
"Darèios89":
Allora significa andare a sommare tutti i nodi ai vari livelli, cioè:
[tex]2^0+2^1+2^2+.....+2^n[/tex]
ok, esatto. Sommare i nodi (di un albero binario) fino ad altezza di difinizione di "nodo interno" cioè ad $h-1$, perciò:
$sum_{i=0}^{h-1} 2^i = (2^((h-1)+1) - 1)/(2-1) = 2^h -1 $
una serie geometrica come hai detto
Ah già....esatto...grazie mille!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo