2016新编堆的遍历与堆排序

《2016新编堆的遍历与堆排序》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、/*最大堆问题，堆数据结构是一颗完全二叉树，用数组来完成其物理实现，逻辑上实际是一种树形结构，r是下标，parent(r)=int((r-1)/2);leftchild(r)=2r+1;rightchild(r)=2r+2;*/以下是头文件maxheap.h的内容templateclassmaxheap{private:Elem*heapArray;intmaxsize;intn;//堆的大小public:maxheap(intsize=10){maxsize=size;heapArray=newElem[maxsize];//

2、注意为中括号n=0;}~maxheap(){delete[]heapArray;}intheapsize(){returnn;}intparent(intpos){return(pos-1)/2;}intleftchild(intpos){return2*pos+1;}intrightchild(intpos){return2*pos+2;}boolinsert(Elem&e);boolremove(intpos);boolcreatHeap(intArrLen,Elem*arr);voidpreorder(intpos);voidheapSort(

3、intarrlen);voidprint();};templateboolmaxheap::insert(Elem&e){if(n>=maxsize-1)returnfalse;heapArray[n]=e;//cout<=0&&heapArray[parent(temp)]

4、Array[temp];heapArray[temp]=ha;//cout<boolmaxheap::creatHeap(intArrLen,Elem*arr){intn=ArrLen;//heapArray=newElem[ArrLen];for(inti=0;i

5、urntrue;}templateboolmaxheap::remove(intpos){if(pos<0

6、

7、pos>n)returnfalse;Elemtemp;temp=heapArray[pos];heapArray[pos]=heapArray[n-1];heapArray[n-1]=temp;n=n-1;//删除一个节点后，堆节点数减1intj=leftchild(pos);while(j<=n-1){if(heapArray[leftchild(pos)]

8、)]&&rightchild(pos)<=n-1)j=rightchild(pos);//此时，j指向孩子中较大节点if(heapArray[pos]>=heapArray[j])break;//如果父节点比左右节点中较大节点大，则循环退出temp=heapArray[j];//父节点与较大节点交换heapArray[j]=heapArray[pos];heapArray[pos]=temp;pos=j;j=leftchild(pos);}returntrue;}templatevoidmaxheap::preord

9、er(intpos)//前序遍历{//cout<voidmaxheap::print(){cout<<"物理实现（数组形式）：";for(inti=0;i

10、<<"逻辑结构基于数组的完全二叉树（最大堆）；"<voi