priority_heap.h

用堆实现优先队列

#ifndef PRIORITY_HEAP_H
#define PRIORITY_HEAP_H

#include<iostream.h>

class ObjectElem{
private:
	int ID;
	int Priority;
public:
	ObjectElem(int objID = -1, int objpri = -1){
		ID=objID;
		Priority=objpri;
	}
    void setID(int objID){ID=objID;}
	void setPriority(int objpri){Priority=objpri;}
	int getID(){return ID;}
	int getPriority(){return Priority;}
};

class Compare{
public:
	static bool lt(ObjectElem l,ObjectElem r){return l.getPriority()<r.getPriority();}
	static bool eq(ObjectElem l,ObjectElem r){return l.getPriority()==r.getPriority();}
	static bool gt(ObjectElem l,ObjectElem r){return l.getPriority()>r.getPriority();}
};

template<class Elem,class Comp>class priorityheap{
	private:
		Elem*Heap;             
		int size;             
		int n;                 
 		int Aux[100];                           //auxiliary array
		void siftdown(int);    
		void swap(Elem*,int,int);
        void printhelp(int,int)const;

	public:
		priorityheap(Elem*h,int num,int max)    //constructor
		{Heap=h;n=num;size=max;buildHeap();}
		~priorityheap(){delete[]Heap;}
		
		void init(){
		delete[]Heap;
		n=0;
		Heap=new Elem[size];
		int i;
		int j;
		int pro;
		cout<<"\n"<<"队列最多容纳元素个数:";
        cin>>size;
        cout<<"\n输入队列元素的个数:";
	    cin>>n;
	    cout<<"\n输入队列元素";
		for( j=0;j<n;j++){
			cout<<"ID:";
		    cin>>i;
            if(i>size){cout<<"出错!ID的输入请在最大容纳个数内!\n";break;}
			Heap[j].setID(i);
			cout<<"优先级:";
			cin>>pro;
			Heap[j].setPriority(pro);
			
		}
		for( j=0;j<n;j++)
        Aux[Heap[j].getID()]=j;
		buildHeap();
		print();
		}                            //init the heap and aux
        
		void buildHeap(){for(int i=n/2-1;i>=0;i--)siftdown(i);} 
		int heapsize()const          //Return current heap size
		{return n;}
		bool isLeaf(int pos)const    //TRUE if pos is a leaf
		{return (pos>=n/2)&&(pos<n);}
		int leftchild(int pos)const
		{return 2*pos+1;}            //Return leftchild position
		int rightchild(int pos)const 
		{return 2*pos+2;}            //Return rightchild position
		int parent(int pos)const     //Return parent position
		{return (pos-1)/2;}
        void enqueue(const int&id,const int&pr)  //enqueue 
		{insert(id,pr);}
		bool insert(const int&,const int&);      //insert into heap
	    int dequeue()                            //Remove the highest priority value
		{   Elem first;
			if(removeHighest(first))
			 return first.getID();
			else return -1;
		}
		bool removeHighest(Elem&);                    //remove the first priority Element
		void changeweight(const int&id,const int&pr)  //change the ID's priority 
		{if(setNewpriority(id,pr))
			cout<<"\n改变成功!\n";
		 else cout<<"\n!未找到ID.\n";
     	}
		bool setNewpriority(const int&,const int&);   //set new priority
		bool remove(int);
		void print()const{
		 if(n==0)cout<<"队列为空.";
		 else 	
			for(int i=0;i<n;i++)
		      cout<<"ID:"<<Heap[i].getID()<<"\t"
			      <<"优先级:"<<Heap[i].getPriority()<<"\n";
			  cout<<"\n";
		}	
		
};

template<class Elem,class Comp>      //Utility function
void priorityheap<Elem,Comp>::siftdown(int pos){
	while(!isLeaf(pos)){             //Stop if pos is a leaf
	int j=leftchild(pos);int rc=rightchild(pos);
	if((rc<n)&&Comp::lt(Heap[j],Heap[rc]))
	j=rc;                            //Set j to smaller chile's value
	if(!Comp::lt(Heap[pos],Heap[j]))
		return;      
	swap(Heap,pos,j);
	pos=j;                           //Move down
	}
}

template<class Elem,class Comp>
void priorityheap<Elem,Comp>::swap(Elem*h,int pos1,int pos2)
{Elem temp;
 temp=h[pos1];
 h[pos1]=h[pos2];
 h[pos2]=temp;              //finish swap
 Aux[h[pos1].getID()]=pos1; 
 Aux[h[pos2].getID()]=pos2; //swap the priority in auxiliary array
}

template<class Elem,class Comp>     //init element
bool priorityheap<Elem,Comp>::insert(const int&id,const int&pr){
 if(n>=size)return false;
 if(id>size){cout<<"出错!ID的输入请在最大容纳个数内!\n";return false;}//Heap is full
 int curr=n++; 
 Heap[curr].setID(id);                    //insert at end of heap
 Heap[curr].setPriority(pr);
 Aux[id]=curr;
 // Now sift up until curr's parent>curr
 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>     //Remove the first Priority ELEM
bool priorityheap<Elem,Comp>::removeHighest(Elem&first){
if(n==0)return false;               //Heap is empty
swap(Heap,0,--n);                   //swap max with last value
if(n!=0)siftdown(0);                //siftdown new root val
first=Heap[n];
return true;                        //Return deletedvalue
}

template<class Elem,class Comp>     
bool priorityheap<Elem,Comp>::setNewpriority(const int&id,const int&newpr){
	if(Aux[id]==-1)return false;
    Heap[Aux[id]].setPriority(newpr);
	remove(Aux[id]);
    return true;
}

template<class Elem,class Comp>     
bool priorityheap<Elem,Comp>::remove(int pos){
	if((pos<0)||(pos>=n))return false;
	while((pos!=0)&&(Comp::gt(Heap[pos],Heap[parent(pos)])))
	{swap(Heap,pos,parent(pos));   //Push up if large key
	 pos=parent(pos);
	}
    siftdown(pos);                 //Push down if small key
	return true;
}

#endif