D4rkAng3l
02-07-2008, 16:44
Sono abbastanza disperato per l'esame di elementi di algoritmi e strutture dati che avrò tra un paio di giorni...mi dite se questo algoritmo è corretto?
Ricordando che un Heap è un albero binario con struttura rafforzata (ovvero un albero binario completo fino al penultimo livello) e dove ogni nodo k ha chiave <= di quella del padre.
Ricordando anche che un heap può essere messo su un vettore posizionale e dove un nodo i ha il figlio sinistro in posizione 2*i, il figlio destro in posizione (2*i+1) ed il padre in posizione (i/2)
Scrivere una funzione aumentaChiave(H, i , k) che imposta H[i] al massimo tra il valore precedente ed il nuovo valore di k, aggiornando la struttura heap appropriatamente.
Io l'ho pensato così:
aumentaChiave(H, i , k){
val = max{k, H[i-1]}
H[i] = val
WHILE(i>1 && H[i] > H[i/2]{
SCAMBIA H[i] CON H[i/2]
i = i/2
}
Così facendo inizialmente metto in val il valore massimo tra il parametro k passato alla funzione e l'elemento H[i-1] che sarebbe proprio l'elemento precedente ad H[i] nell'array H.
Poi l'elemento val deve essere messo in H[i], successivamente tramite il ciclo WHILE lo faccio eventualmente risalire qualora la modifica appena effettuata violasse la proprietà degli heap per cui la chiave del padre deve sempre essere maggiore della chiave dei figli.
L'elemento potrebbe subire una serie di scambi che lo può portare al più nella locazione 1 dell'array che corrisponderebbe alla radice dell'albero (la locazione 0 è settata vuota per far partire a memorizzare da 1 per rendersi più facili le formule del figlio sinistro, destro e del padre).
Quindi nel caso peggiore i è una locazione dell'array che rappresenta una foglia e viene fatto risalire fino alla radice.
e quindi la complessità sarebbe O(H) con H= altezza albero heap
Ci può stà?
Tnx
Andrea
Ricordando che un Heap è un albero binario con struttura rafforzata (ovvero un albero binario completo fino al penultimo livello) e dove ogni nodo k ha chiave <= di quella del padre.
Ricordando anche che un heap può essere messo su un vettore posizionale e dove un nodo i ha il figlio sinistro in posizione 2*i, il figlio destro in posizione (2*i+1) ed il padre in posizione (i/2)
Scrivere una funzione aumentaChiave(H, i , k) che imposta H[i] al massimo tra il valore precedente ed il nuovo valore di k, aggiornando la struttura heap appropriatamente.
Io l'ho pensato così:
aumentaChiave(H, i , k){
val = max{k, H[i-1]}
H[i] = val
WHILE(i>1 && H[i] > H[i/2]{
SCAMBIA H[i] CON H[i/2]
i = i/2
}
Così facendo inizialmente metto in val il valore massimo tra il parametro k passato alla funzione e l'elemento H[i-1] che sarebbe proprio l'elemento precedente ad H[i] nell'array H.
Poi l'elemento val deve essere messo in H[i], successivamente tramite il ciclo WHILE lo faccio eventualmente risalire qualora la modifica appena effettuata violasse la proprietà degli heap per cui la chiave del padre deve sempre essere maggiore della chiave dei figli.
L'elemento potrebbe subire una serie di scambi che lo può portare al più nella locazione 1 dell'array che corrisponderebbe alla radice dell'albero (la locazione 0 è settata vuota per far partire a memorizzare da 1 per rendersi più facili le formule del figlio sinistro, destro e del padre).
Quindi nel caso peggiore i è una locazione dell'array che rappresenta una foglia e viene fatto risalire fino alla radice.
e quindi la complessità sarebbe O(H) con H= altezza albero heap
Ci può stà?
Tnx
Andrea