PDA

Visualizza la versione completa : [ALGORITMO] Costruzione heap con procedura bottom-up


dennis87
28-05-2012, 15:27
Salve ragazzi, mi potreste aiutare a capire come funziona quest'ordinamento?
Questo è l'esempio che viene fatto e che non capisco
http://s7.imagestime.com/out.php/i719046_Capture.PNG (http://www.imagestime.com/show.php/719046_Capture.PNG.html)
Grazie a tutti

Mond0
28-05-2012, 15:45
per quello che ricordo la funzione heapsort ha il compito di trasformare un vettore in un heap. Quindi l'elemento in posizione i avrà i figli in posizione 2*i+1 e 2*i+2.
Detto ciò il primo for ordina in modo che ogni padre ha i figli con valore + basso (quindi ad esempio l'elemento 2 ha un valore maggiore dell'elemento 5 e 6). Parte dal primo nodo che non è una foglia (quindi appunto da n/2). la funzione downheap sarà qualcosa tipo:


void downheap(int A[], int i, int heapsize){
int l,r, largest;
l = LEFT(i); //figlio sinistro
r = RIGHT(i); //figlio destro
if(l<heapsize && A[l]>A[i])
largest = l;
else largest = i;
if (r<heapsize && A[r]>A[largest])
largest = r;
if (largest != i){
Swap(A, i, largest);
downheap(A, largest, heapsize);
}
return;

nel while invece scambia il primo elemento con l'ultimo e ripete l'operazione di rimettere in ordine i valori...

Who am I
28-05-2012, 16:03
Ti manca di effettuare il controllo che non si esca dagli indici dell' array, e poi non ho capito perché la procedura la richiami solo su largest.

dennis87
28-05-2012, 16:07
ho capito il suo funzionamento. Grazie a tutti..

Mond0
28-05-2012, 16:12
Originariamente inviato da Who am I
Ti manca di effettuare il controllo che non si esca dagli indici dell' array, e poi non ho capito perché la procedura la richiami solo su largest.

se largest != i allora c'è stato uno spostamento di valori, quindi ricorro nel sottoalbero opportuno per verificare che, dopo tale spostamento, le proprietà dell'heap continuino ad essere rispettate. la funzione downheap non "sale" mai, ma mette "a posto" dal nodo (indice) passato fino al fondo dell'array.

Loading