Posted on 2012-09-15 14:40
C小加 閱讀(2676)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
數(shù)據(jù)結(jié)構(gòu)和算法 、
模板
template<class T,int MAX=100003>
class BinaryHeap
{
private:
int Size;
T * Tarr;
public:
BinaryHeap();
void insert(T x);
T deleteMin();
~BinaryHeap();
};
template<class T,int MAX>
BinaryHeap<T,MAX>::BinaryHeap()
{
Tarr=new T[MAX+1];
if(Tarr==NULL) {cout<<"創(chuàng)建數(shù)組失敗"<<endl;return ;}
Size=0;
}
template<class T,int MAX>
void BinaryHeap<T,MAX>::insert(T x)
{
++Size;
if(Size==MAX) return;
int i;
for(i=Size;Tarr[i/2]>x;i/=2)
Tarr[i]=Tarr[i/2];
Tarr[i]=x;
}
template<class T,int MAX>
T BinaryHeap<T,MAX>::deleteMin()
{
if(Size==0) return 0;
T minem=Tarr[1];
T lastem=Tarr[Size--];
int i,child;
for(i=1;i*2<=Size;i=child)
{
child=i*2;
if(child!=Size-1&&Tarr[child+1]<Tarr[child])
++child;
if(lastem>Tarr[child])
Tarr[i]=Tarr[child];
else
break;
}
Tarr[i]=lastem;
return minem;
}
template<class T,int MAX>
BinaryHeap<T,MAX>::~BinaryHeap()
{
delete[] Tarr;
}