//Gonzalez ortega carlos	  
//materia: Estructura de Datos	Grupo  : 2802
//Profesor: Rubio Alejandro	
//  Programa que realiza ordenacion por el Metodo de Heap Short       

#include "stdio.h"
#include "conio.c"
#define N 100	/*maximo de elementos*/

main(){
int a[N];
int n,i,elt,s,f,ivalue;
	clrscr();
    gotoxy(20,2); printf("Ordenacion por el Metodo de Heap Sort");
	gotoxy(5,6);printf("Introduzca el tamaņo del arreglo: ");
	gotoxy(5,40);scanf("%d", &n);/*lee el tama¤o del arreglo*/
    gotoxy(5,8);printf("Valores del arreglo: ");
	for (i=1; i<=n; i++)
		{gotoxy(i*4+1,9);scanf("%d", &a[i]);}/*lee y almacena los elementos en el arreglo principal*/
/* inserta en monticulo*/ 
for(i=1;i<=n;i++)
{
elt=a[i];
s=i;
f=(s-1)/2;
while ((s>0)&&(a[f]<elt))
{
a[s]=a[f];
s=f;
f=(s-1)/2;
}/* fin del while*/
a[s]=elt;
}/* fin del for*/
for(i=n;i>=1;i--)
{
ivalue=a[i];
a[i]=a[0];
f=0;
if (i==1)
s=-1;
else
s=1;
if ((i>2)&&(a[2]>a[1]))
s=2;
while ((s>=0)&&(ivalue<a[s]))
{
a[f]=a[s];
f=s;
s=2*f+1;
if ((s+1<=i-1)&&(a[s]<a[s+1]))
s=s+1;
if (s>i-1)
s=-1;
} /* fin del while*/
a[f]=ivalue;
}/* fin del for*/

 gotoxy(5,12); printf("El arreglo ordenado es: ");
	for (i=1; i<=n; i++)
		printf("%d  ", a[i]);/*Imprime el arreglo ordenado*/
	getch();
  return 0; 
}


/*************************************************/