#include<iostream.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<stdio.h>

const int n=10000;

typedef struct{
	int key;
}RedType;

typedef struct{  
RedType  *r;       //r[n+1];
int length;
}SqList;



int random();
void HeapSort(SqList &R,int m);
void main(){ 
	
    int t,m;
  	SqList L;
	L.r = new RedType[n+1];
	L.length=n;
	for(int i=1;i<=n;i++)	L.r[i].key=random();
	long t1,t2;	
	t=1;
	m=n;
	t1=clock();
    HeapSort(L,n);
	t2=clock();
	cout<<" 時(shí)間: "<<float(t2-t1)/CLK_TCK<<endl;
//	for(i=1;i<=n;i++)
//		cout<<L.r[i].key<<endl;
	
	
}
int random(){
    	int A=48271;
	int M=2147483647;
	int Q=M/A;
	int R=M%A;
	static int x=1;	int x1;
	x1=A*(x%Q)-R*(x/Q);
	if(x1>=0) x=x1;
	else	x=x1+M;
	return x;
}

void Sift(SqList &R,int p,int q)
{
	int j;
	R.r[0]=R.r[p];
	j=2*p;
	while(j<=q)
	{
		if(j<q&&R.r[j].key<R.r[j+1].key)j++;
		if(R.r[0].key>R.r[j].key)break;
		R.r[p]=R.r[j];
		p=j;
		j=2*p;
	}
	R.r[p]=R.r[0];
}

void HeapSort(SqList &R,int m){       //對(duì)R[1]到R[n]進(jìn)行堆排序
int i;
for(i=m/2;i>=1;i--) Sift(R,i,m);     //建初始堆
for(i=m;i>=2;i--){              //進(jìn)行n-1趟堆排序
R.r[0]=R.r[1];                   //堆頂和當(dāng)前堆底交換,R[0]作輔助量
R.r[1]=R.r[i];
R.r[i]=R.r[0];
Sift(R,1,i-1);                 //R[1]到R[i-1]重建成新堆
}
}// HeapSort