/* *	堆排序2007-04-17 14:17堆排序(Heap Sort) * * *	1.	基本思想： *			堆排序是一樹形選擇排序，在排序過程中，將R[1..N]看成是一顆完全二叉樹的順序存儲結構 *			利用完全二叉樹中雙親結點和孩子結點之間的內在關系來選擇最小的元素。 * * *	2.	堆的定義: N個元素的序列K1,K2,K3,...,Kn.稱為堆，當且僅當該序列滿足特性： *			Ki≤K2i * *			Ki ≤K2i+1(1≤ I≤ [N/2]) * *		堆實質上是滿足如下性質的完全二叉樹： *			樹中任一非葉子結點的關鍵字均大于等于其孩子結點的關鍵字。 *			例如序列10,15,56,25,30,70就是一個堆。這種堆中根結點（稱為堆頂）的關鍵字最小，我們把它稱為小根堆。 *			反之，若完全二叉樹中任一非葉子結點的關鍵字均大于等于其孩子的關鍵字，則稱之為大根堆。 * * *	3.	排序過程： *			堆排序正是利用小根堆（或大根堆）來選取當前無序區中關鍵字小（或最大）的記錄實現排序的。 *			我們不妨利用大根堆來排序。 *			每一趟排序的基本操作是： *				將當前無序區調整為一個大根堆，選取關鍵字最大的堆頂記錄，將它和無序區中的最后一個記錄交換。 *				這樣，正好和直接選擇排序相反，有序區是在原記錄區的尾部形成并逐步向前擴大到整個記錄區。 * * *	用大根堆排序的基本思想 *		① 先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區 *		② 再將關鍵字最大的記錄R[1](即堆頂)和無序區的最后一個記錄R[n]交換， *			由此得到新的無序區R[1..n-1]和有序區R[n]，且滿足R[1..n-1].keys≤R[n].key *		③ 由于交換后新的根R[1]可能違反堆性質，故應將當前無序區R[1..n-1]調整為堆。 *			然后再次將R[1..n-1]中關鍵字最大的記錄R[1]和該區間的最后一個記錄R[n-1]交換， *			由此得到新的無序區R[1..n-2]和有序區R[n-1..n]， *			且仍滿足關系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調整為堆。 *			...... *			直到無序區只有一個元素為止。 * *		① Heapify函數思想方法 *			每趟排序開始前R[l..i]是以R[1]為根的堆，在R[1]與R[i]交換后， *			新的無序區R[1..i-1]中只有R[1]的值發生了變化，故除R[1]可能違反堆性質外， *			其余任何結點為根的子樹均是堆。因此，當被調整區間是R[low..high]時，只須調整以R[low]為根的樹即可。 *		"篩選法"調整堆 *			R[low]的左、右子樹(若存在)均已是堆，這兩棵子樹的根R[2low]和R[2low+1]分別是各自子樹中關鍵字最大的結點。 *			若R[low].key不小于這兩個孩子結點的關鍵字，則R[low]未違反堆性質，以R[low]為根的樹已是堆，無須調整； *			否則必須將R[low]和它的兩個孩子結點中關鍵字較大者進行交換， *			即R[low]與R[large](R[large].key=max(R[2low].key，R[2low+1].key))交換。 *			交換后又可能使結點R[large]違反堆性質，同樣由于該絒large]為根的樹進行調整。 *			此過程直至當前被調整的結點已滿足堆性質，或者該結點已是葉子為止。 *			上述過程就象過篩子一樣，把較小的關鍵字逐層篩下去，而將較大的關鍵字逐層選上來。 *			因此，有人將此方法稱為"篩選法"。 */ #include <math.h>#include <stdio.h>#include <stdlib.h>#include <string.h>#include <errno.h>#include <time.h>#include <sys/time.h>#define MAXSIZE 1000000 //排序表的最大容量typedef struct		//定義排序表的結構{	int elemword[MAXSIZE+1];		//數據元素關鍵字	int length;					//表中當前元素的個數}SqList;void InitialSqList(SqList&);		//初始化排序表void HeapSort(SqList &);			//堆排序void HeapAdjust(SqList &,int,int);	//堆調整void PrintSqList(SqList);			//顯示表中的所有元素int main(void){	struct timeval time_point;	SqList L;			//聲明表L		InitialSqList(L);	//待排序列初始化	gettimeofday( &time_point, NULL );	printf( "\n開始 秒：%d 微妙: %d\n", time_point.tv_sec, time_point.tv_usec );	HeapSort(L);		//堆排序	gettimeofday( &time_point, NULL );	printf( "結束 秒：%d 微妙: %d\n", time_point.tv_sec, time_point.tv_usec );	PrintSqList(L);		//顯示排序結果	return( 0 );}void InitialSqList( SqList &L ){	FILE	*fp = NULL;	char	indata[32];	if( (fp=fopen("indata","r")) == NULL )	{		fprintf( stderr, "fopen() error. strerror(errno)=%s\n", strerror(errno) );		exit( -1 );	}	memset( &L, 0, sizeof(SqList) );	memset( indata, 0, sizeof(indata) );	while( fgets( indata, sizeof(indata), fp ) != NULL )	{		if( indata[strlen(indata)-1] == '\n' )			indata[strlen(indata)-1] = '\0';		L.length++;		L.elemword[L.length] = atoi( indata );		memset( indata, 0, sizeof(indata) );	}	fclose( fp );}void HeapSort(SqList &L){	//對順序表L做堆排序	int i,j,t;	for( i=L.length/2; i>0; --i )		//把L.elemword[1..L.length]建成大頂堆		HeapAdjust( L, i, L.length );	for( i=L.length; i>1; --i )	{		t = L.elemword[1];				//將堆頂記錄和當前未經排序子序列L.elemword[1..i]		L.elemword[1] = L.elemword[i];	//中的最后一個記錄相互交換		L.elemword[i] = t;		HeapAdjust( L, 1, i-1 );		//將L.r[1..i-1]重新調整為大頂堆	}}void HeapAdjust(SqList &H,int s,int m){	//已知H.elemword[s..m]中除H.elemword[s]之外均滿足堆的定義,本函數調整H.elemword[s]	//使H.elemword[s..m]成為一個大頂堆	int j,rc;	rc=H.elemword[s];	for(j=2*s;j<=m;j*=2)	//沿關鍵字較大的結點向下篩選	{		if(j<m&&H.elemword[j]<H.elemword[j+1]) ++j; //j為關鍵字較大的記錄的下標		if(rc>=H.elemword[j]) break; //rc應插入在位置s上		H.elemword[s]=H.elemword[j];		s=j;	}	H.elemword[s]=rc;	//插入}void PrintSqList( SqList L ){		//顯示表中所有元素	FILE *fp = NULL;	if( (fp=fopen("outdata","w")) == NULL )	{		fprintf( stderr, "fopen() error. strerror(errno)=%s\n", strerror(errno) );		exit( -1 );	}	for( int i=1; i<=L.length; i++ )		fprintf( fp, "%d\n", L.elemword[i] );	fclose( fp );}