template<typename Type>
struct Great{
bool operator()( Type a, Type b ){
return a> b; }
};
template<typename Type>
struct Less{
bool operator()( Type const& a, Type const& b ){
return a< b; }
};
#define SIZE 10010
template<typename Type, typename Cmp>
class priority_queue{
private:
Type d[SIZE];
public:
void push( Type const& item ){
int pos= ++*d;
while( pos>>1 >= 1 && Cmp()( d[pos>>1], item ) )
d[pos]= d[pos>>1], pos>>=1;
d[pos]= item;
}
void pop(){
Type tmp= d[d[0]--]; int p= 1;
for( int q= p<<1; q<= *d; q<<= 1 ){
if( q+ 1<= *d && !Cmp()( d[q+1], d[q] ) ) q++;
if( !Cmp()( tmp, d[q] ) ) break;
d[p]= d[q]; p= q;
}
d[p]= tmp;
}
priority_queue(){ *d= 0; }
Type top() { return d[1]; }
int size() { return *d; }
bool empty(){ return *d== 0; }
void clear(){ *d= 0; }
};
// 声明为 priority_queue<Type, Great<Type> > test 时为小顶堆
// 声明为 priority_queue<Type, Less<Type> > test 时为大顶堆
posted on 2009-04-20 18:28
Darren 阅读(831)
评论(0) 编辑 收藏 引用