heapfunction.cpp

算法实验:1 分治法在数值问题中的应用 ——最近点对问题 2 减治法在组合问题中的应用——8枚硬币问题 3 变治法在排序问题中的应用——堆排序 4 动态规划法在图问题中的应用——全源最短路径问题

#include "heap.h"

//构建大顶堆
void HeapBottomUP(Array *H){
	int i,j,k,v;
	bool heap;
	for(i=(*H).len/2-1;i>=0;i--){
		k=i;v=(*H).a[k];//v要放在最终位置
		heap=false;
		while( !heap && 2*k+2<(*H).len ){
			j=2*k+2;
			if(j<(*H).len)//有两个孩子
				if((*H).a[j-1]>(*H).a[j])
					j-=1;
			if(v>=(*H).a[j])
				heap=true;
			else{
				(*H).a[k]=(*H).a[j];
				k=j;
			}
		}//while
		(*H).a[k]=v;
	}//for
}

//堆排序
void HeapSort(Array *H){
	int i,j,k,v;
	bool heap;
	for(i=(*H).len-1;i>0;i--){
		v=(*H).a[i];
		(*H).a[i]=(*H).a[0];
		heap=false;
		j=0;
		while( !heap && 2*j+1<i){
			k=j;
			j=2*k+2;
			if(j<i ){
				if( (*H).a[j-1] >(*H).a[j] )
					j-=1;
			}else{
				if(i==1){
					j=0;
					heap=true;
					break;
				}
				else j-=1;
			}
			if(v<(*H).a[j])
				(*H).a[k]=(*H).a[j];
			else {
				heap=true;
			}
		}//
		if(heap)
			(*H).a[k]=v;
		else (*H).a[j]=v;
	}//for
}

//输入待排序数据
void Input(Array *H){
	printf("请输入待排序数的个数(小于%d):\n",MAX);
	scanf("%d",&(*H).len);
	int i;
	for(i=0;i<(*H).len;i++)
		scanf("%d",&((*H).a[i]));
}

void AutoData(Array *H){
	printf("请输入待排序数的个数(小于%d):",MAX);
	scanf("%d",&(*H).len);
	int i;
	srand( (unsigned int)time(0) );
	for(i=0;i<(*H).len;i++)
		(*H).a[i]=rand()%50;
}

//输出排序结果
void Output(Array H){
	int i;
	for(i=0;i<H.len;i++)
		printf("%-3d",H.a[i]);
	printf("\n");
}

void HeapStart(){
	Array H;
	char c;
	int k;
begin:
	system("cls");
	printf("选择工作方式(1 手动输入  2 自动产生数据):\n");
	scanf("%d",&k);
	if(k==1)
		Input(&H);
	else
		AutoData(&H);
	printf("排序前:\n");
	Output(H);
	HeapBottomUP(&H);
	HeapSort(&H);
	printf("排序后:\n");
	Output(H);
	printf("继续测试?(y/n)");
	while( getchar()!='\n' );
	c=getchar();
	
	if(c=='y')
		goto begin;
}