salve gente. Questo è il mio primo thread.
Il mio problema riguarda l'implementazione di un algoritmo stra conosciuto, ovvero l' heap.
si tratta di un grafo che all' apparenza si presenta disordinato, ma che usato nel modo giusto è ordinato per certi aspetti e permette di usare meno ci cicli computazionali rispetto ad un normale ordinamento insertion-sort che impiega n^2.
guardando lo pseudo codice, ho scritto in C il seguente codice:
CODICE
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 3
int riempi_vettore(int *A, int n){
int i;
srand(time(NULL));
for(i=0;i<n;i++){
A[i]=rand()%20; // casuali tra 0 e 20
}
}
int stampa_vettore(int *A, int n){
int i;
for(i=0;i<n;i++){ printf("%d ", A[i]); }
}
int sinistro(int i){
i=((2*i)+1);
return i;
}
int destro(int i){
i=(2*(i+1));
return i;
}
int heapify(int *A, int i){
int l,r;
int maggiore,tmp;
l=sinistro(i);
r=destro(i);
if( l<N && A[l] > A[i] ){
maggiore=l;
}
else{ maggiore=i; }
if( r<N && A[r] > A[maggiore] ){
maggiore=r;
}
if( maggiore!=i){
tmp=A[i];
A[i]=A[maggiore];
A[maggiore]=tmp;
heapify(A,maggiore);
}
}
int main(){
int vettore[N];
riempi_vettore(vettore,N);
stampa_vettore(vettore,N);
heapify(vettore,0);
printf("\n ordinato \n\n");
stampa_vettore(vettore,N);
system("pause");
}
come si può vedere dall' inizio, ho posto N = 3 tanto per cominciare, poi volevo provare 7 e poi vedere se anche con heap incompleti il tutto funziona.
il codice postato funziona perfettamente, ma solo nei caso in cui N=3. con N=4, 5, 6.....etc non funziona per niente.
Qualcuno è cosi gentile da spiegarmi cosa effettivamente sbaglio????
le mie ipotesi sono le seguenti:
1) nella main io richiamo heapify(vettore,0) -> ma è giusto mettere 0?
2) nello pseudocodice c'è heah-size[A] che magari è una funzione a parte, io ho posto direttamente N,
