最大堆和最小堆.txt

一些很好用的数据结构

template <class Elem，class Comp> class MinHeap  {
private :
    Elem * heap;   //存放堆元素的数组
    int n;   //堆当前元素个数
    int size;  //堆最多允许元素个数
     void siftdown (int i) 
public :
    MinHeap (Elem* h, int num ,int max)           //构造堆
     {Heap=h; n=num; size=max; buildHeap();}
    int heapsize() const {return n;}
    ~MinHeap( ) {delete [ ] heap;}
    bool  Insert (const Elem & );
    bool RemoveMin (Elem & );
    bool isLeaf(int pos) const{return (pos>=n/2)&&(pos<n)}
    int leftchild(int pos) const {return pos*2+1;}
    int rightchild(int pos) const {return pos*2+2;}

int parent(int pos) const{return (pos-1)/2;}
bool remove(int,  Elem&);
void buildHeap()
   {
    for(int i=n/2-1; i>=0; i--) 
     siftdown(i); 
 } 
};



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

template <class Elem，class Comp>
bool  MinHeap<ELem,Comp> :: Insert(const Elem & val){
        if (n = = Size) 
              return false;
     int curr=n++;     while((curr!=0)&&(Comp::lt(Heap[curr],Heap[Parent(curr)])))
{
   swap(Heap,curr,parent(curr));
   curr=parent(curr);
 }
 return true;
}
templat <class Elem,class Comp>bool MinHeap<Elem,Comp> ::    RemoveMin(Elem &it ){
    if (n==0)  return false;
    swamp(Heap,0,--n);
   if(n!=0) siftdown(0);
   it=Heap[n];
   return true;
}

template<class Elem, class Comp> bool MinHeap<Elem,Comp>::
remove(int pos,Elem& it){
  if((pos<0)||(pos>=n) return false;
   swap( Heap, pos, --n);
   while((pos!=0)&&(Comp::lt(Heap[pos],Heap[parent(pos)])))
        swam(Heap,pos,parent(pos));
  siftdown(pos);
  it=Heap[n];
  return true;
}





















 


template <class Elem,class Comp> class maxHeap 
{
private :
    Elem * Heap;   //存放堆元素的数组
    int n;   //堆当前元素个数
    int size;  //堆最多允许元素个数
    void siftdown (int i); 
public :
    maxHeap (Elem* h, int num ,int max)           //构造堆
	{Heap=h; n=num; size=max; buildHeap();}
    int heapsize() const {return n;}
    bool  Insert (const Elem & );
    bool Removemax (Elem & );
    bool isLeaf(int pos) 
	{
		return ((pos>=n/2)&&(pos<n));
	}
    int leftchild(int pos) const {return pos*2+1;}
    int rightchild(int pos) const {return pos*2+2;}
	
	int parent(int pos) const{return (pos-1)/2;}
	bool remove(int,  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>::Insert(const Elem & val){
	if (n >= Size) 
		return false;
	int curr=n++;    Heap[curr]=val; 
	while((curr!=0)&&(Comp::gt(Heap[curr],Heap[Parent(curr)])))
	{
		swap(Heap,curr,parent(curr));
		curr=parent(curr);
	}
	return true;
}
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;
}

template<class Elem, class Comp> 
bool maxHeap<Elem,Comp>::remove(int pos,Elem& it)
{
	if((pos<0)||(pos>=n)) return false;
	swap( Heap, pos, --n);
	while((pos!=0)&&(Comp::gt(Heap[pos],Heap[parent(pos)])))
        swap(Heap,pos,parent(pos));
	siftdown(pos);
	it=Heap[n];
	return true;
}