数据结构例题 堆排序.doc

《数据结构例题 堆排序.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构例题堆排序#include#defineMAX255intR[MAX];voidHeapify(ints,intm){/*对R[1..n]进行堆调整，用temp做暂存单元*/intj,temp;temp=R[s];j=2*s;while(j<=m){if(R[j]>R[j+1]&&j

2、堆*/inti;for(i=n/2;i>0;i--)Heapify(i,n);}voidHeap_Sort(intn){/*对R[1..n]进行堆排序，不妨用R[0]做暂存单元*/inti;BuildHeap(n);/*将R[1-n]建成初始堆*/for(i=n;i>1;i--){/*对当前无序区R[1..i]进行堆排序，共做n-1趟。*/R[0]=R[1];R[1]=R[i];R[i]=R[0];/*将堆顶和堆中最后一个记录交换*/Heapify(1,i-1);/*将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质*/}/*endoff

3、or*/}/*endofHeap_Sort*/voidmain(){inti,n;clrscr();puts("Pleaseinputtotalelementnumberofthesequence:");scanf("%d",&n);if(n<=0

4、

5、n>MAX){printf("nmustmorethan0andlessthan%d.",MAX);exit(0);}puts("Pleaseinputtheelementsonebyone:");for(i=1;i<=n;i++)scanf("%d",&R[i]);puts("Thesequen

6、ceyouinputis:");for(i=1;i<=n;i++)printf("%4d",R[i]);Heap_Sort(n);puts("ThesequenceafterBigheap_sortis:");for(i=1;i<=n;i++)printf("%4d",R[i]);puts("Pressanykeytoquit...");getch();}publicclassMaxHeap{privateElemh,intnum,intmax){Heap=h;n=num;size=max;buildheap();}publicinthea

7、pSize(){returnn;}publicbooleanisLeaf(intpos){return(pos>=n/2)&&(pos

8、(intpos){Assert.notFalse(pos>0,"Positionhasnoparent");return(pos-1)/2;}publicvoidbuildheap(){for(inti=n/2-1;i>=0;i--)siftdown(i);}privatevoidsiftdown(intpos){Assert.notFalse((pos>=0)&&(pos

9、y()=Heap.key())return;Dsutil.swap(Heap,pos,j);pos=j;}}publicvoidinsert(Elemval){Assert.notFalse(nHeap.key())){Dsutil.swap(Heap,curr,parent(curr));curr=parent(curr);}}publicElem

10、removemax(){Assert.notFalse(n>0,"RemovingfromemptyHeap");Dsut