//                         max-heap sort in c++//                        最大值堆排序算法实现//作者：Andyhou #include <iostream>using namespace std; //建立比较类。class initCompare{public: static bool it(int x,int y) {  return x<y; } static bool gt(int x,int y) {  return x>y; } static bool eq(int x,int y) {  return x==y; }};//Max-heap class template <class Elem,class Compare>class maxheap{private: Elem* Heap; int size; int n; void siftdown(int); void swap(Elem A[],int,int);public: maxheap(Elem* h,int num,int max) {  Heap=h;  n=num;  size=max;  buildHeap(); } int heapsize() const {  return n; } bool isLeaf(int pos) const {  return (pos>=n/2)&&(pos<n); } int leftchild(int pos) const {  return 2*pos+1; } int rightchild(int pos) const {  return 2*pos+2; } int parent(int pos) const {  return (pos-1)/2; } bool insert(const Elem&); bool removemax(Elem&); bool remove(int ,Elem&); void buildHeap() {  for(int i=n/2-1;i>=0;i--)   siftdown(i); } void heapsort(Elem A[],int n);}; template<class Elem,class Compare>void maxheap<Elem,Compare>::swap(Elem A[],int i,int j){ Elem temp=A[i]; A[i]=A[j]; A[j]=temp;}template <class Elem,class Compare>void maxheap<Elem,Compare>::siftdown(int pos){ while(!isLeaf(pos)) {  int j=leftchild(pos);  int rc=rightchild(pos);  if((rc<n)&&Compare::it(Heap[j],Heap[rc]))   j=rc;  if(!Compare::it(Heap[pos],Heap[j]))   return ;  swap(Heap,pos,j);  pos=j; }} template<class Elem,class Compare>bool maxheap<Elem,Compare>::insert(const Elem& item){ if(n>=size)  return false; int curr=n++; Heap[curr]=item; while((curr!=0)&&(Compare::gt(Heap[curr],Heap[parent(curr)]))) {  swap(Heap,curr,parent(curr));  curr=parent(curr); } return true;}//删除最大值把最大值往数组后面移动。template<class Elem,class Compare>bool maxheap<Elem,Compare>::removemax(Elem& val){ if(n==0) return false; swap(Heap,0,--n); if(n!=0)   siftdown(0); val=Heap[n]; return true;} template<class Elem,class Compare>bool maxheap<Elem,Compare>::remove(int pos,Elem& it){ if((pos<0)||(pos>=n))  return false; swap(Heap,pos,--n); while((pos!=0)&&(Compare::gt(Heap[pos],Heap[parent(pos)])))  swap(heap,pos,parent(pos)); siftdown(pos); it=Heap[n]; return true;}//最大值堆排序template<class Elem,class Compare>void maxheap<Elem,Compare>::heapsort(Elem A[],int n){ Elem mval; for(int i=0;i<n;i++)  removemax(mval);} int main(){  int n; cout<<"Enter the sum of number: "; cin>>n; int* array=new int[n]; cout<<"Enter the number: "; for(int i=0;i<n;i++)  cin>>array[i]; maxheap<int,initCompare>A(array,n,n);//初始化最大值堆。 A.heapsort(array,n); cout<<"after sort print all number!"; for(i=0;i<n;i++)  cout<<array[i]<<"  "; cout<<endl; return 0;} 注：    最大值堆排序比较适应大型的数据排序和外排序：      

评论