堆的建立和筛选.cpp

堆的建立和筛选 实现堆排序 数据结构初学者可以参考

/* 
这个算法的实现没有按照书上的做法,书的算法变量太多,且命名混乱,不容易分析和理解,所以我采用了严蔚敏版的算法. 
另外,书中在排序开始时是讲,所有的排序都是从小到大的排序,但现在的做法是将小的结点放在了数组的后面,又没有说明. 
*/ 
//#include "stdafx.h" 
#include <iostream> 
#include <malloc.h> 

using namespace std;

int const count=8; 

typedef struct 
{ 
	int key; 
}records; 

typedef records list[count+1]; 

//堆的首结点调整 
//在r中,大于s的节点都已经满足堆的性质,即r[s+1],r[s+2]..r[m],只有r[s]是使堆不成立的结点,那么这里就只调整它 
void HeapAdjust(list & r,int s,int m) 
{ 
	//记录初始的值,以便在适当的位置将其插入到其它位置,而将此子树下的最大结点放在r[s]中 
	int key=r[s].key; 
	//这里用j<=m,是因为j=m即是上一个结点的一个左孩子,那么因为有左孩子则也是需要进行比较的 
	//如果在进到入循环时,j>m,则说明上次循环的j便是叶子结点了 
	for(int j=2*s;j<=m;j*=2) 
	{ 
		//这里用j<m,是用来判断上一个结点也即父结点,是否有左孩子和右孩子,如果没有右孩子,则只需要比较父结点和左孩子的值即可 
		//如果上个父结点有左/右孩子,则需要比较这两个左右孩子,然后判断左孩子是否小于右孩子,如果小于,则让j++,使r[j]指向的是 
		//较大的右孩子的结点,使其从大的方向继续查找 
		if (j<m && r[j].key<r[j+1].key) 
		{ 
			j++; 
		} 
		//判断初始结点是否大于这一次循环中最大的r[j]的值,如果大于,则说明目前已经符合堆的性质了,那么退出循环 
		if (key>r[j].key) 
		{ 
			break; 
		} 
		//将上次的父结点改为这次较大结点的,即交换了父结点与孩子结点,然后另下次循环的父结点指向这次的较大结点 
		r[s].key=r[j].key; 
		s=j; 
	} 
	//将首个使堆不成立的结点插入到合适的位置 
	r[s].key=key; 
} 

/**//* 
学习堆排序首先要搞清楚完全二叉树的性质和特点. 
在完全二叉树中,可对各层进行编号,编号排列的结果就是一个一维的数组,这个一维的树组也正是我们这里要排序的数组 
如果只有这个树组,那么这个数组所对应的完全二叉树之间有这样的关系:所有的父结点必需是不大于n/2的值,所以在首次建堆的时候,从以count/2开始,然后一层层的建堆. 
另外,对于第i个元素,2i是它的左子树,2i+1是它的右子树,如果2i>n,则这个结点没有左子树,同理2i+1>n则这个结点没有右子树,这在heapAdjust 
中有着重要的意义,这是用来判断循环结束,以及确定延哪个子结点方向继续调整的关键 
*/ 
void HeapSort(list & r) 
{ 
	int i; 
	//首次建堆.从count/2,即从第1个非页子结点来建树.然后一级级的建树,直至整个树符合堆的性质 
	for(i=count/2;i>0;i--) 
	{ 
		HeapAdjust(r,i,count); 
		if(i==1)
		{
			cout<<"第1趟调整之后堆顶元素"<<r[1].key<<endl;
		}
		
	} 
	for(i=count;i>1;i--) 
	{ 
		//将数组的本次循环的最末元素与堆的首个元素交换,而这个堆的首个元素即除了已摘除的元素中,最大的无素. 
		int key=r[1].key; 
		r[1].key=r[i].key; 
		r[i].key=key; 
		//调用调整堆调整方法 
		HeapAdjust(r,1,i-1); 
		cout<<"第"<<count-i+2<<"趟调整之后堆顶元素"<<r[1].key<<endl;

	} 
} 

void printList(list r) 
{ 
	for(int i=0;i<count;i++) 
	{ 
		if (i==0) 
		{
			cout<<r[i+1].key; 
		} 
		else 
		{ 
			cout<<","<<r[i+1].key; 
		} 
	} 
	cout<<endl; 
} 

int main() 
{ 
	list r; 
/**//* 
for(int i=0;i<count;i++) 
{ 
cout<<"输入第"<<i+1<<"个主键"; 
cin>>r[i+1].key; 
} 
*/ 
	r[1].key=70; 
    r[2].key=73; 
    r[3].key=69; 
    r[4].key=23; 
    r[5].key=93; 
    r[6].key=18; 
    r[7].key=11; 
    r[8].key=68; 
	cout<<"输入的序列为:"<<endl; 
    printList(r); 
	
	HeapSort(r); 
	cout<<"排序后的序列为:"<<endl; 
	printList(r); 
	return 0; 
}