posts - 274, comments - 1258, trackbacks - 0

例程：PQ API

#include < algorithm >

// 本例程介绍了STL heap的用法，并将其封装到到一个优先队列类中

const int maxLen = 100 ;

template < class T >

#define DEAP // 浅复制还是深复制

struct PQ { // 最大堆

T h[maxLen];

int e;

void clear() { e = 0 ;}

bool empty() { return e == 0 ; }

int size() { return e;}

void push( const T & item) { // O(logN)

h[e ++ ] = item;

push_heap(h,h + e);

}

T & pop() { // O(logN)

pop_heap(h,h + e);

return h[ -- e];

}

const T & top() {

return h[ 0 ];

}

void make(T * bgn, T * end) { // O(N)

#ifdef DEAP // 深复制

for (e = 0 ; bgn != end; ++ e, ++ bgn)

h[e] =* bgn;

#else // 浅复制

e = end - bgn;

memcpy(h,bgn,e * sizeof ( * bgn));

#endif

make_heap(h,h + e);

}

void sort(T * bgn) { // O(NlogN)

#ifdef DEAP // 深复制

int i; T * end = bgn;

for (i = 0 ; i < e; ++ i, ++ end)

* end = h[i];

#else // 浅复制

T * end = bgn + e;

memcpy(bgn,h,e * sizeof ( * bgn));

#endif

sort_heap(bgn, end);

}

friend bool isHeap(T * bgn, T * end) { // debug用, O(N)

T * h = bgn - 1 ; int i,e = end - bgn + 1 ;

for (i = 2 ; i < e; ++ i)

if (h[i / 2 ] < h[i]) return false ;

return true ;

}

PQ() { clear();}

} ;

#include < cassert >

#include < iostream >

using namespace std;

template < class T >

inline void show(T a[], int n) {

int i;

for (i = 0 ; i < n; ++ i)

cout << a[i] << ' ' ;

cout << endl;

}

// 简单测试

int main() {

PQ < int > pq;

int a[] = { 3 , 6 , 5 , 4 , 2 , 7 , 9 } ;

cout << (pq.empty() ? " Empty\n " : " Not empty\n " );

pq.make(a,a + sizeof (a) / sizeof ( * a));

show(pq.h,pq.size());

cout << " Top: " << pq.top() << endl;

cout << ( isHeap(pq.h, pq.h + pq.e) ? " Is heap\n " : " Not a heap\n " );

pq.push( 3 );

pq.push( 1 );

pq.push( 10 );

show(pq.h,pq.size());

cout << " Top: " << pq.top() << endl;

cout << ( isHeap(pq.h, pq.h + pq.e) ? " Is heap\n " : " Not a heap\n " );

cout << " Pop: " << pq.pop() << endl;

pq.sort(a);

show(a,pq.size());

return 0 ;

}

posted on 2006-07-09 10:11 踏雪赤兔阅读(632) 评论(2) 编辑收藏引用所属分类: 零件仓库

FeedBack:

# re: 例程：PQ API

2006-07-16 01:51 | ling

阅读排行榜第一名居然一条评论都没有，睇黎我吾系第一个睇吾明的，考完仲系吾明堆的用法回复更多评论

# re: 例程：PQ API

2006-07-17 14:39 | 踏雪赤兔

　　哈哈~~堆是有一点难学~但是它真的很有用啊~俾多点心机就行啦。
　　这段程序与其说是一个标程，更不如说是一个例程。说它是标程是因为它封装了一个PQ类（Piority Queue优先队列）PQ类最基本的操作有两个：push和pop。push与栈或队列类似，都是将元素添加到容器中；但pop就不同了，它每次弹出的是值最大（小）的元素，而跟push的顺序关系不大。
　　说它是例程，是因为它实际上是STL　heap的一个演示。STL heap比较容易用错（我最近才将一个最大堆当了最小堆来用-_-!!!)使用时需要注意以下几点：
　　1）定义小于的是最大堆，定义大于的是最小堆;
　　2）进行push时，先++再push: push_heap(h,h+(++e));
　　3）进行pop时，先pop再--: pop_heap(h,h+(e--));
　　4）最大堆排序(sort_heap)是升序的，最小堆排序是降序的。
　　有不明白再问吧。回复更多评论

刷新评论列表

只有注册用户登录后才能发表评论。