aiuto con algoritmo di ordinamento

[algoritmogoloso]

ragazzi
ho questo algoritmo scritto in java e volevo sapere come funziona, se potete spiegarmi brevemente cosa fa e come funziona e come posso testarlo..vi ringrazio in anticipo!

ps: ho già eclipse sul pc!

public class heap {
	protected int[] A;
	protected int heapSize;
	
	public heap(){
		A=new int[50];
		heapSize=0;
	}
	public boolean insertIn(int i, int key)
	{
		if(A[i]==0 && heapSize<A.length){
			A[i]=key;
			heapSize++;
			return true;
		}
		else
			return false;
	}
	protected void exch(int i, int t)
	{
		int temp=A[i];
		A[i]=A[t];
		A[t]=temp;
	}
	private int left(int i){
		return (2*i);
	} 
	private int right(int i){
		return (2*i+1);
	}
	protected int parent(int i){
		return (i/2);
	}
	public void printArray(int l){
		int i;
		System.out.println("");
		for(i=1;i<=l;i++){
			System.out.print(A[i]);
			System.out.print("  ");
		}		
	}
	public void maxHeapify(int i)
	{
		int max;
		int l = left(i);
		int r = right(i);		
		if(l <= heapSize && A[l]>A[i])
			max=l;
		else
			max=i;
		
		if(r<=heapSize && A[r]>A[max])
			max=r;
		
		if(max!=i){
			exch(i,max);
			maxHeapify(max);
		}
	}	
	public void buildHeap()
	{
		int i;
		for(i=heapSize/2; i>0; i--)
			maxHeapify(i);
	}	
	public void heapSort()
	{
		int i;
		buildHeap();
		for(i=heapSize;i>=2;i--)
		{
			exch(1,i);
			heapSize--;
			maxHeapify(1);
		}
	}
}

[klaussss]

Allora la struttura dati che tu hai davanti è un HEAP.E' un albero binario dove ogni nodo ha due figli(destro(right) la cui chiave ha valore minore rispetto a quella del padre e sinistro(left) la cui chiave ha valore maggiore rispetto a quella del padre) a cui puoi accedere tramite le due funzioni left e right(puoi facilmente verificare con carta e penna costruendoti un albero binario il perchè degli indici che sono ritornati).Tramite la funzione parent tu puoi ottenere il padre del nodo in esame.
La prima cosa che devi fare è istanziare un elemento della classe nel main(heap h=new heap() in questo modo inizializzi un array di 50 elementi e heapsize(cardinalità del tuo heap).Tramite la funzione insert inizi a riempire il tuo array.Infine puoi passare a riordinare il tuo array per trasformarlo in un HEAP ricordandoti le proprietà dell'heap.
Per maggiori spiegazioni posta pure o puoi consultare:
http://it.wikipedia.org/wiki/Heap

[algoritmogoloso]

Originariamente inviato da klaussss
Allora la struttura dati che tu hai davanti è un HEAP.E' un albero binario dove ogni nodo ha due figli(destro(right) la cui chiave ha valore minore rispetto a quella del padre e sinistro(left) la cui chiave ha valore maggiore rispetto a quella del padre) a cui puoi accedere tramite le due funzioni left e right(puoi facilmente verificare con carta e penna costruendoti un albero binario il perchè degli indici che sono ritornati).Tramite la funzione parent tu puoi ottenere il padre del nodo in esame.
La prima cosa che devi fare è istanziare un elemento della classe nel main(heap h=new heap() in questo modo inizializzi un array di 50 elementi e heapsize(cardinalità del tuo heap).Tramite la funzione insert inizi a riempire il tuo array.Infine puoi passare a riordinare il tuo array per trasformarlo in un HEAP ricordandoti le proprietà dell'heap.
Per maggiori spiegazioni posta pure o puoi consultare:
http://it.wikipedia.org/wiki/Heap

allora,
grazie innanzitutto per aver risposto subito!!
però mi sa che devo correggerti. in un albero binario il figlio sinistro ha valore minore del padre e del fratello mentre il figlio destro ha valore maggiore... o sbaglio?

vorrei chiederti un altro favore.. se quotando pezzo pezzo del codice puoi dirmi cosa fanno le singole procedura... te ne sarei veramente grato!! perchè non ci ho capito molto

[klaussss]

Si hai ragione scusami è da un pò che non tocco questi argomenti per cui mi sono sbagliato tra figlio destro e sinistro.Allora rispondendo alla tua seconda domanda:
public heap(){
A=new int[50];
heapSize=0;
}
Questo è il costruttore all'atto dell'istanziazione di un elemento della classe heap viene inizializzato un array di 50 elementi e un intero (heapSize) a 0.

public boolean insertIn(int i, int key)
{
if(A[i]==0 && heapSize<A.length){
A[i]=key;
heapSize++;
return true;
}
else
return false;
}

Questa funzione booleana ritorna il valore booleano true(vero) se l'inserimento è andato a buon fine(cioè hai ancora spazio nel tuo array e l'elemento che desideri inserire viene posto nel primo elemento che ha chiave uguale a 0) altrimenti ritorna false(falso) nel caso in cui il tuo array sia pieno.

protected void exch(int i, int t)
{
int temp=A[i];
A[i]=A[t];
A[t]=temp;
}

questa funzione non credo possa crearti problemi è una normalissima funzione di scambio con l'ausilio di una variabile ausiliaria(temp).

private int left(int i){
return (2*i);
}
private int right(int i){
return (2*i+1);
}
protected int parent(int i){
return (i/2);
}

queste funzioni ti permettono di ottenere l'indice del figlio sinistro destro e del padre di un generico nodo i.

public void printArray(int l){
int i;
System.out.println("");
for(i=1;i<=l;i++){
System.out.print(A[i]);
System.out.print(" ");
}
}

funzione di stampa degli elementi di un array.(anche questa credo che tu l'abbia vista molte volte)

public void maxHeapify(int i)
{
int max;
int l = left(i);
int r = right(i);
if(l <= heapSize && A[l]>A[i])
max=l;
else
max=i;

if(r<=heapSize && A[r]>A[max])
max=r;

if(max!=i){
exch(i,max);
maxHeapify(max);
}
}

questa funzione è il corpo effettivo della tua classe heap e esamina l'elemento i-esimo con i suoi figli e pone (se esiste) l'elemento maggiore in i e l'elemento minore in uno dei suoi figli. Infine si richiama su l'eventuale nodo figlio con il quale è stato fatto lo scambio e quindi contiene l'elemento minore.

public void buildHeap()
{
int i;
for(i=heapSize/2; i>0; i--)
maxHeapify(i);
}

questa funzione ti permette di costruire il tuo heap e in questo caso come puoi osservare il for inizia dalla metà della lunghezza del tuo heap in quanto gli altri elementi saranno già ordinati e le proprietà del tuo heap saranno rispettate dalla maxheapify.

public void heapSort()
{
int i;
buildHeap();
for(i=heapSize;i>=2;i--)
{
exch(1,i);
heapSize--;
maxHeapify(1);
}
}

In sostanze l'HeapSort prende il primo elemento (il più grande) e lo scambia con l'ultimo. L'ultimo finendo in prima posizione "corrompe" la struttura dell'Heap, quindi viene chiamato Heapify per ricomporre l'Heap di (n-1) elementi. Ricorsivamente questa procedura ordina "dal fondo" e quindi alla fine l'array è ordinato.

[algoritmogoloso]

perfetto!! grazie!! sei stato gentilissimo!!!

ma se voglio provarlo come devo fare? voglio testarlo con un array disordinato.. e voglio vedere l'output... come si fa? grazie!

[klaussss]

Perdona la domanda ma quanto conosci di programmazione e quanto conosci di java? Che problema hai nell'usare il seguente algoritmo?

[algoritmogoloso]

come avrai ben capito ne so davvero poco!

voglio solo eseguire quell'algoritmo e provarlo con un array disordinato in modo da vedere se funziona bene e se mi dà l'array ordinato

scusa se chiedo troppo

[klaussss]

Crea una istanza della tua classe:
heap h=new heap();
poi esegui un for
for(int i=0;i<50;i++)
h.insert(i,x)//con x ho indicato il generico valore che tu vuoi inserire
e poi passi ad eseguire le operazioni di ordinamento spero di essere stato chiaro

p.s. se posso farti una domanda cosa studi?