/*****************************************************/
/* Nom: Ansen Pierre                                 */
/* Groupe: 2125                                      */
/* ex : Heap Sort - Tri arbre                        */
/*                                                   */
/* Date: 31/01/2010                                  */
/*****************************************************/

# include <stdio.h>
# include <stdlib.h>
# define MAX 100

void heapsort (float *, int);
void paterner (float *, int, int);
void affiche (float *, int);
void encode (float *, int);

void main ()
{
	float vec[MAX];
	int nbel, test;

	do
	{
		printf("Entrez le nombre d'elements: ");
		fflush(stdin);
		test=scanf("%d",&nbel);
	} while (test==0 || nbel > MAX || nbel <1);

	/* fonction qui permet d'encoder le vecteur */
	encode (&vec[0],nbel);

	system ("cls");

	/* fonction qui permet d'afficher le vecteur */
	printf("Voici votre vecteur:\n");
	affiche (&vec[0],nbel);

	/* fonction qui construit le heap sort et tri */
	heapsort (&vec[0],nbel);

	/* fonction qui permet d'afficher le vecteur */
	printf("\n\nVoici votre vecteur apres le heap sort et le tri:\n");
	affiche (&vec[0],nbel);

	printf("\n\n");

}

/**************************************************************/
/* I: pvec: adresse du vecteur                                */
/*    nbl: nombre d'éléments dans le vecteur                  */
/* P: donne des valeurs à chaque élément du vecteur           */
/* O: ///                                                     */
/**************************************************************/

void encode (float *pvec, int nbl)
{
	int test,i=0;

	while (i<nbl)
	{
		do
		{
			printf("Entrez la valeur pour la case %d: ",i);
			fflush(stdin);
			test=scanf("%f",pvec);
		}while (test==0);
		i++;
		pvec++;
	}
}

/**************************************************************/
/* I: pvec: adresse du vecteur                                */
/*	  nbl: nombre d'éléments dans le vecteur                  */
/* P: Affiche le vecteur									  */
/* O: ///											      	  */
/**************************************************************/

void affiche (float *pvec, int nbl)
{
	int i=0;

	while (i<nbl)
	{
		printf("%.0f   ",*pvec);
		i++;
		pvec++;
	}
}

/***************************************************************/
/* I: pvec: adresse du vecteur                                 */
/*	  ipere: variable utilisé pour distinguer le père des fils */
/*	  nbl: nombre d'éléments dans le vecteur                   */
/* P: Paterner le vecteur, chaque père est plus grand que ses  */
/*	  deux fils												   */
/* O: ///											           */
/***************************************************************/

void paterner (float *pvec, int ipere,int nbl)
{
	int ifils;
	float temp;

	temp=*(pvec+ipere-1);
	ifils=ipere*2;

	while (ifils<=nbl)
	{
		if (ifils<nbl && *(pvec+ifils)>*(pvec+ifils-1))
		{
			ifils=ifils+1;
		}

		if (*(pvec+ifils-1)>temp)
		{
			*(pvec+ipere-1)=*(pvec+ifils-1);
			ipere=ifils;
			ifils=ipere*2;
		}
		else
		{
			ifils=nbl+1;
		}
	}
	*(pvec+ipere-1)=temp;
}

/**************************************************************/
/* I: pvec: adresse du vecteur                                */
/*	  nbl: nombre d'éléments dans le vecteur                  */
/* P: Appelle à la fonction pour paterner successivement      */
/*	  de sorte à avoir un père plus grand que ses deux fils   */
/* O: ///												      */
/**************************************************************/

void heapsort (float *pvec, int nbl)
{
	int i;
	float temp;

	i=nbl/2;
	while (i>=1)
	{
		paterner (pvec,i,nbl);
		i--;
	}

	i=nbl;
	while (i>1)
	{
		temp=*(pvec);
		*(pvec)=*(pvec+i-1);
		*(pvec+i-1)=temp;
		i--;
		paterner (pvec,1,i);
	}
}