#include<iostream.h>
enum ResultCode{Overflow,Underflow};

template<class T>
class PrioQueue
{
public:
PrioQueue(int mSize);
~PrioQueue(){delete []q;};
void Append(const T& x);
void Serve(T& x);
bool IsEmpty() const{return n==0;}
bool IsFull() const{return n==maxSize;}

void Output(ostream& out)const;
void AdjustDowm(int r,int j);
void AdjustUp(int j);
private:
T *q;
int n,maxSize;
friend ostream &operator<<(ostream & out,const PrioQueue<T>& s);
};
template<class T>
PrioQueue<T>::PrioQueue(int mSize)
{
maxSize=mSize;
n=0;
q=new T[maxSize];
}
template<class T>
void PrioQueue<T>::AdjustUp(int j)
{
int i=j;T temp=q[i];
while(i>0&&temp<q[(i-1)/2])
{
q[i]=q[(i-1)/2];i=(i-1)/2;
}
q[i]=temp;
}
template<class T>
void PrioQueue<T>::AdjustDowm(int r,int j)
{
int i=2*r+1;
T temp=q[r];
while(i<=j)
{
if((i<j)&&(q[i]>q[i+1])) i++;
if(temp<=q[i])break;
q[(i-1)/2]=q[i];
i=2*i+1;
}
q[(i-1)/2]=temp;
}


template<class T>
void PrioQueue<T>::Append(const T& x)
{
if(IsFull())throw Overflow;
q[n++]=x;
AdjustUp(n-1);
}
template<class T>
void PrioQueue<T>::Serve(T &x)
{
if(IsEmpty())throw Underflow;
x=q[0];q[0]=q[--n];
AdjustDown(0,n-1);
}
template<class T>
void PrioQueue<T>::Output(ostream& out)const
{
out<<endl<<"The PrioQueue contains:";
for(int i=0;i<n;i++)
out<<q[i]<<" ";

}
template<class T>
ostream &operator<<(ostream& out,const PrioQueue<T>& s)
{
s.Output(out);
return out;
}
void main()
{
try{
PrioQueue<int>a(10);
a.Append(71);
a.Append(74);
a.Append(2);
a.Append(72);
a.Append(54);
a.Append(93);
a.Append(52);
a.Append(28);
cout<<a<<endl;

}
catch(ResultCode err)
{
switch(err)
{
case Overflow:cout<<"Overflow!"<<endl;break;
case Underflow:cout<<"Underflow!"<<endl;break;
}
}

[此贴子已经被作者于2006-4-21 22:05:04编辑过]