#include <cstdio>
#include <iostream>
#include <vector>
#include <utility>
#include <cstdlib>
#include <sys/time.h>
using namespace std;
void heapsort(int n, int *ary)
{
ary--;
for(int i = n/2; i>=1; i--) {
int j = i;
while(true) {
int nj = j;
if((j<<1)+0<=n && ary[nj]<ary[(j<<1)+0]) nj=(j<<1)+0;
if((j<<1)+1<=n && ary[nj]<ary[(j<<1)+1]) nj=(j<<1)+1;
if(nj==j)break;
swap(ary[j], ary[nj]);
j = nj;
}
}
while(n>0) {
swap(ary[1], ary[n--]);
int j = 1;
while(true) {
int nj = j;
if((j<<1)+0<=n && ary[nj]<ary[(j<<1)+0]) nj=(j<<1)+0;
if((j<<1)+1<=n && ary[nj]<ary[(j<<1)+1]) nj=(j<<1)+1;
if(nj==j)break;
swap(ary[j], ary[nj]);
j = nj;
}
}
return;
}
void sorttest(int asize) {
int *ary = (int*)malloc(sizeof(int)*asize);
timeval s,t;
for(int i = 0; i < asize; i++) {
ary[i] = rand();
}
printf("%d elems:\n",asize);
gettimeofday(&s, NULL);
heapsort(asize, ary);
gettimeofday(&t, NULL);
for(int i = 0; i < 10; i++) {
printf("%d, ", ary[i]);
}
printf("...\n");
printf("%fs\n\n", (t.tv_sec-s.tv_sec)+(t.tv_usec-s.tv_usec)/1000000.0);
free(ary);
}
int main(int argc, char **argv)
{
srand(1000);
sorttest(10);
sorttest(100);
sorttest(1000);
sorttest(10000);
sorttest(100000);
sorttest(1000000);
sorttest(3000000);
sorttest(10000000);
sorttest(30000000);
return 0;
}