#include <sys/time.h>
#include "heapsort.h"
#include "crearreglo.h"


#define key(A) (A)
#define less(A, B) (key(A) < key(B))
#define pq(A) a[A-1]
#define exch(A, B) { int t = A; A = B; B = t; } 

void fixDown(int a[], int k, int N)
{
int j;
while (2*k <= N)
	{ j = 2*k;
        if (j < N && less(a[j], a[j+1])) j++;
        if (!less(a[k], a[j])) break;
        exch(a[k], a[j]); k = j;
      	}
}

/* algoritmo heapsort, que llama a funcion copiarreglo en el 75% de la 
ejeucion aproximadamente*/

void heapsort_2(int *parcial,int a[], int N)
{
int k,numero;
	for (k = N/2; k >= 1; k--) 
		fixDown(&pq(0), k, N);
	numero=N;
	if(N==numero/8) copiarreglo(parcial,a,numero);
	while (N > 1) 
      		{
		if(N==numero/4) copiarreglo(parcial,a,numero);
      		exch(pq(1), pq(N)); 
       		fixDown(&pq(0), 1, --N);
		}
  }


/*algoritmo heapsort sort que entrega el tiempo [usec] que se 
demora en ordenar el arreglo A de tamaņo n.El tipo devuelto
es long*/

long heapsort(int a[], int N)
{
int k;
struct timeval q,r;
 
gettimeofday(&q,0);
for (k = N/2; k >= 1; k--) 
	fixDown(&pq(0), k, N);
while (N > 1) 
      	{
	exch(pq(1), pq(N)); 
        fixDown(&pq(0), 1, --N);
	}
gettimeofday(&r,0);
return((r.tv_sec*1000000+r.tv_usec)-(q.tv_sec*1000000+q.tv_usec)); 
  }