Newsgroup: it.comp.lang.c
Titolo: heapsort

ciao a tutti,
ho delle difficolta ad implementare l'algoritmo heapsort in linguaggio
ANSI-C
qualcuno potrebbe aiutarmi!
ringrazio anticipatamente
Luca

qualcuno potrebbe aiutarmi!
Vai su 
www.google.com
 e cerca "heapsort C".
-- 
The Follet

Finalmente un bell' esercizio. E che pecchato che a causa
crach di vecchio hard disk ho perso la mia versione funzionante
scritta 5 anni fa.
Spero che tu abbi il Sedgewick sotto mano. Head Sort e' una
conseguenza delle proprieta' della struttura dati Heap. Sul
Sedgewich si chiama "Coda con priorita'".
Devi scrivere due funzioni di base per la gestione dello Heap
(e non quello di sistema, piuttosto inteso come struttura dati
cosi come lo definisce Sedgewich (Terza citazione!))
La funzione UpHeap() inserisce in fondo al mucchio un nuovo
elemento, poi risale per collocarlo nella posizione che gli
spetta secondo le proprieta' che poi vedremo.
La funzione DownHeap() che preleva dalla cima del mucchio
l' elemento con "priorita' piu' alta" (devi tu definire il
criterio di priorita') e discende lo heap per promuovere a
vertice il secondo elemento di priorita' piu' alta.
HeapSort consiste nel chiamare per tutti gli elementi della
lista disordinata UpHeap() e poi chiamare DownHeap() fino
a che non svuoti interamente lo Heap. LA SEQUENZA CON CUI SVUOTI
LO HEAP CHIAMANDO DownHeap() E' ORDINATA SECONDO IN CRITERIO
CHE TU HAI STABILITO!! Cambiando il concetto di priorita'
puoi ordinare in modo invertito, case insensitive ecc...
Le due funzioni possono essere implementate in vari modi: il
piu semplice e' realizzare lo heap in un array o con file ad
accesso random. Ogni elemento e' da considerarsi LOGICAMENTE
correlato ad altri due (se esistenti) di priorita' sicuramente
piu' bassa o uguale di esso, e ad un "padre" con priorita piu'
alta o uguale ad esso. Li puoi schematizzare come albero binario,
ma se realizzi tutto con struttura dari ad accesso random non hai
bisogno di usare effettivamente i puntatori. Per trovare il
relatico di priorita' piu' alta di ogni nodo dividi l' indice
per 2 (anche se dispari), per trovare i due relativi di priorita'
piu' bassa moltiplichi per 2 (primo) e poi +1 (secondo).
Pero' devi gestire gli indici da 1 e non da 0, quindi quando
una divisione da 0 l' elemento e' di MAX priorita' se una
moltiplicazione per 2 va oltre il numero degli elementi inseriti
fino a quel momento, non ha uno e entrambi i "figli" di priorita'
inferiore. Lo heap non e' ordinato. Semplicemente conserva sempre
questa proprieta'.
Non e' semplice da spiegare cosi'. Ti rimando a Sedgewich per la
Quarta volta.
Mi ci vorranno alcuni giorni a riscrivere il codice. Non chiedermelo.
Ciao
Roberto


 qualcuno potrebbe aiutarmi!
su 
http://ioi.dsi.unimi.it
 trovi delle dispense che spigano la 
struttura dati heap. Da quelle non dovrebbe esserti difficile 
implementare l'heapsort.
ciao anto
-- 
Antonio Cuni, 19 anni, studente
Brainbench C++ Master: 4.6, higher than 98% of all previous test takers.
C Language: 3.32, higher than 79% of all previous test takers.
Guida C/C++ di Programmazione.it: 
http://cpp.programmazione.it

Heap sort ha un costo 3*log2 N ed e' di costo stabile a differenza
di quiksort che puo' avere casi degeneri. A differenza di mergesort
di costo 2*log2 N, non richiede la copia del file o array da ordinare.
Per me Merge sort e Fichissssssimo...
P.S. 
ziof...@mypad.com
 e defunto (nel senso di provider 
mypad.com
)
Al suo posto c' e':
el-g...@el-guapo.cjb.net
 cioe' Roberto Cappellini
Ciao a tutti.
Roberto.

 ANSI-C qualcuno potrebbe aiutarmi!
eccoti il codice, funziona. se non capisci qualcosa chiedimi che ti
spiego :-)
#include <stdio.h>
void creaheap(int *,int);
void heap(int *,int,int);
void scambia(int *,int *);
void stampa();
int main(void)
{
	int array[10] = {5,2,8,1,9,4,3,7,6,1};
	int i;
	int dimensione = 9;
	stampa(array);
	creaheap(array,dimensione);
	for (i=9;i>1;i--)
	{
		scambia(&array[0],&array[i]);
		dimensione--;
		heap(array,0,dimensione);
	}
	printf("\nArray ordinato:\n");
	stampa(array);
	getchar();
	return 0;
}
void creaheap(int array[],int n)
{
	int i,k;
	k = n/2;
	for (i=k;i+1>0;i--)
	{
		heap(array,i,n);
		printf("\n");
		stampa(array);
	}
	printf("\n");
	stampa(array);
}
void heap(int array[],int n,int dimensione)
{
	int maggiore,s,d;
	s = (n + 1) * 2 - 1;
	d = (n + 1) * 2;
	if (s <= dimensione && array[s] > array[n])
		maggiore = s;
	else
		maggiore = n;
	if (d <= dimensione && array[d] > array[maggiore])
		maggiore = d;
	if (maggiore != n)
	{
		scambia(&array[n],&array[maggiore]);
		heap(array,maggiore,dimensione);
	}
}
void scambia(int *a,int *b)
{
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
}
void stampa(int array[])
{
	int i;
	int dimensione = 10;
	for (i=0;i<dimensione;i++)
		printf("%d ",array[i]);
}

 del file o array da ordinare.
anche mergesort... scusa, avrai dimenticato una n davanti al logaritmo
altrimenti sarebbe un algoritmo di una velocità assurda...

 wrote in message
3bf2cdac...@news.libero.it...


Si Si! Ho dimenticato il coefficiente moltiplicativo
N pe rtutte le difinizioni. Sorry.
Se un giorno vi faccio credere che posso ordinare 4200000000
di record in 32 passi, picchiatemi come ciarlatano.
Un costo log2 N ce l' ha una sola chiamata a UpHeap().
Una chiamata a DownHeap() ha costo 2 log2 N perche' si devono
fare due confronti con i due figli per sapere chi dei due
promuovere e siccome bisogna chiamare N volte UpHeap()
per costruire l' heap e N volte Downheap() per avere la sequenza
ordinata l' algoritmo ha costo 3*N*log2 N come hai detto.
In realta' un po' meno perche' la maggior parte delle chiamate
e' fatta su heap ancora non completo degli N elementi e quindi
il log2 I all' I esimo passo e' <= a lon2 N, ma visto che il
logaritmo chesce prima molto, poi poco il costo e' piu' prossimo
a 3*N* log2 N.
Scusate se sono andato lungo, ma era doveroso riparare all' errore.
Ho visto che nella tua implementazione non hai organizzato il codice
formalizzando UpHeap() e DownHeap(). Che sia anche piu' efficiente??
Ciao
Roberto.