heapsort.h

这算法实现了插入排序

template<class Elem,class Comp>
void heapsort(Elem A[],int n) {
	Elem mval;
	maxheap<Elem,Comp>H(A,n,n);
	for(int i=0;i<n;i++)
	H.removemax(mval);
}
template <class Elem,class Comp>
class maxheap{
private:
	Elem* Heap;
	int size;
	int n;
	void siftdown(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;
	}
	bool parent(int pos) const {
	  return (pos-1)/2;
	}
	bool removemax(Elem&);
    void buildHeap(){
	  for(int i=n/2-1;i>=0;i--)
		  siftdown(i);
	}
};

template <class Elem,class Comp>  
void maxheap<Elem,Comp>::siftdown(int pos){    
      while(!isLeaf(pos)){
	   int j=leftchild(pos);
	   int rc=rightchild(pos);
	   if((rc<n)&&Comp::lt(Heap[j],Heap[rc]))
		   j=rc;   
	   if(!Comp::lt(Heap[pos],Heap[j]))
		   return;
	   swap(Heap,pos,j);  
	   pos=j;
	}
}

template <class Elem,class Comp>  
bool maxheap<Elem,Comp>::removemax(Elem& it){
  if(n==0)
	  return false;
  swap(Heap,0,--n);  
  if(n!=0)
	  siftdown(0);   
      it=Heap[n];
  return true;
}