heapsort.cpp

堆排序

/*
 *	堆排序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 );
}