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

				/* 
				这个算法的实现没有按照书上的做法,书的算法变量太多,且命名混乱,不容易分析和理解,所以我采用了严蔚敏版的算法. 
				另外,书中在排序开始时是讲,所有的排序都是从小到大的排序,但现在的做法是将小的结点放在了数组的后面,又没有说明. 
				*/ 
				//#include "stdafx.h" 
				#include  
				#include  
				
				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					//如果在进到入循环时,j>m,则说明上次循环的j便是叶子结点了 
					for(int j=2*s;j					{ 
						//这里用j						//如果上个父结点有左/右孩子,则需要比较这两个左右孩子,然后判断左孩子是否小于右孩子,如果小于,则让j++,使r[j]指向的是 
						//较大的右孩子的结点,使其从大的方向继续查找 
						if (j						{ 
							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						}
						
					} 
					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				
					} 
				} 
				
				void printList(list r) 
				{ 
					for(int i=0;i					{ 
						if (i==0) 
						{
							cout						} 
						else 
						{ 
							cout						} 
					} 
					cout				} 
				
				int main() 
				{ 
					list r; 
				/**//* 
				for(int i=0;i				{ 
				cout				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				    printList(r); 
					
					HeapSort(r); 
					cout					printList(r); 
					return 0; 
				}