堆的遍历与堆排序.doc

/*最大堆问题，堆数据结构是一颗完全二叉树，用数组来完成其物理实现，逻辑上实际是一种树形结构，r是下标，parent(r)=int(r-1)/2);leftchild(r)=2r+1;rightchild(r)=2r+2;*/以下是头文件maxheap.h的内容templateclass maxheapprivate:Elem* heapArray;int maxsize;int n;/堆的大小public:maxheap(int size = 10)maxsize = size;heapArray = new Elemmaxsize;/注意为中括号n = 0;maxheap() delete heapArray;int heapsize() return n;int parent(int pos) return (pos-1)/2;int leftchild(int pos) return 2*pos+1;int rightchild(int pos) return 2*pos+2;bool insert(Elem& e);bool remove(int pos);bool creatHeap(int ArrLen,Elem* arr);void preorder(int pos);void heapSort(int arrlen);void print();templatebool maxheap:insert(Elem& e)if(n=maxsize-1)return false;heapArrayn = e;/cout=0 & heapArrayparent(temp)heapArraytemp)ha = heapArrayparent(temp);heapArrayparent(temp) = heapArraytemp;heapArraytemp = ha;/coutheapArraytempheapArrayparent(temp);temp = parent(temp);n +=1;return true;templatebool maxheap:creatHeap(int ArrLen, Elem* arr)int n = ArrLen;/heapArray = new ElemArrLen;for(int i = 0; iArrLen-1 & arri; i+)insert(arri);return true;templatebool maxheap:remove(int pos)if(posn)return false;Elem temp;temp = heapArraypos;heapArraypos = heapArrayn-1;heapArrayn-1 = temp;n = n-1;/删除一个节点后，堆节点数减1int j = leftchild(pos);while(j=n-1)if( heapArrayleftchild(pos) heapArrayrightchild(pos) & rightchild(pos) = heapArrayj )break;/如果父节点比左右节点中较大节点大，则循环退出temp = heapArrayj; /父节点与较大节点交换heapArrayj = heapArraypos;heapArraypos = temp; pos = j;j = leftchild(pos);return true;templatevoid maxheap:preorder(int pos) /前序遍历/coutpos ;coutheapArrayposendl;if(leftchild(pos)n)preorder(leftchild(pos);if(rightchild(pos)n)preorder(rightchild(pos);templatevoid maxheap:print()cout物理实现（数组形式）：;for(int i = 0; in; i+)coutheapArrayi ;coutendl;cout逻辑结构基于数组的完全二叉树（最大堆）；endl;templatevoid maxheap:heapSort(int arrlen)for(int i = 0; iarrlen-1; i+)remove(0);cout堆排序：endl;for(i = 0; iarrlen-1; i+)coutheapArrayiendl;以下是usemaxheap.cpp的内容#include#includemaxheap.husing namespace std;int main()maxheap mymaxheap1(1024);int arr=4,8,25,3,91,54,24,36,74,15,11,8,97,102,114,125,33;mymaxheap1.creatHeap(17,arr);mymaxheap1.print();cout前序遍历:endl;mymaxheap1.preorder(0);mymaxheap1.hea