#include <iostream.h>
#include <time.h>
#include <stdlib.h>
#include <windows.h>
#include "head.h"


void heapsort(array A[],int length)
{
	int t;
	makeheap(A,length);
	for(int j=length;j>=2;j--)
	{
		t=A[1].data;
		A[1].data=A[j].data;
		A[j].data=t;
		t=A[1].num;
		A[1].num=A[j].num;
		A[j].num=t;
		sift_down(A,j-1,1);
	}
}


void makeheap(array A[],int length)
{
	for(int i=length/2;i>=1;i--)
	{
		sift_down(A,length,i);
	}
}

void sift_down(array A[],int k,int i)
{
	int done=0, t;
	if(i>k/2)
	{
		return;
	}
	else
	{
		while(i<=k/2&&done==0)
		{
			i=2*i;
			if(i+1<=k&&A[i+1].data>A[i].data)
			{
				i=i+1;
			}
			if(A[i/2].data<A[i].data)
			{
				t=A[i/2].data;
				A[i/2].data=A[i].data;
				A[i].data=t;
				t=A[i/2].num;
				A[i/2].num=A[i].num;
				A[i].num=t;
			}
			else
			{
				done=1;
			}
		}
	}
}