[ALGORITMO] Costruzione heap con procedura bottom-up

[dennis87]

Salve ragazzi, mi potreste aiutare a capire come funziona quest'ordinamento?
Questo è l'esempio che viene fatto e che non capisco

Grazie a tutti

[Mond0]

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]

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]

ho capito il suo funzionamento. Grazie a tutti..

[Mond0]

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.