没什么好写的，都在《Introduction to Algorithms》里面，老外的教材就是厉害，不像我们国内，计算机类书籍不少，优点是：一、贵，二、内容不全，有时候要学个什么东西查一本书还不行，唉，写书都是为了赚钱，哪有什么好书。 前些天我借了本《算法设计与分析》的书，读着读着发觉怎么好像读过，一想，哦，是这本书里看过，那时候觉得看英文累，印象深刻，原来写中文书还有这么一招，直接翻译来就OK。老外不喜欢东搞西搞，一本书，比砖头还厚，把想说的全说完，全部搞定，简单，容易查阅，买一本一辈子带身边。哈哈，我刚好有一本，影印版的。 这个Priority Queue原来学《数据结构》的时候老师没讲，自己也没重视，现在翻出来学，发现很有用的。 一般的queue都是FIFO，元素间的前后关系完全取决于入队的时间，而不是某种数学上的偏序关系。而现实中的队列却是有优先级的，按优先级排个序，最先出来的应该是优先级最高的，这个时候的queue有个新名字，heap。 按我自己的理解，一个heap就是一个具有某种偏序关系的有序集合，它是一种半‘排序’化状态，我们感兴趣的就是第一个从heap里出来的元素，这时它是最小的，但是你要一次让第k小的出来，做不到，因为它内部组织数据的时候没有完全有序，并不是那么简单的。为什么只需要知道最小元素呢，因为它是一个Priority Queue。 像消息队列就应该是一个Priority Queue，有系统消息，各种用户级别的消息等。 另外像有的时候在需要动态维持一个有序集，同时又需要求最小元素时，很适合使用。像Dijkstra单源点最短路径算法中就可以用Priority Queue优化算法，还有最小生成树算法等。 Priority Queue有很多种，最简单的二叉堆，还有Binomial Heap,Fibonacci Heap等。它们的效率各不相同，优点各异，二叉堆在实现上比较简单，而且重要的操作，像Extract_Min()（取最小元素并移出队列）,Insert()等，都有较好的时间复杂度，但是缺点是Union()操作太废时，这本书上说是O(n)的，而且就给了一句话：By concatenating the two arrays that hold the binary heaps to be merged and then running Min_Heapify,the Union operation takes O(n) time in the worst case.前面的是准确界O(n)。我还不明白这个heap怎么merge，反正感觉不好并。而Binomial Heap就是一种基于‘二进制’和Union()操作的堆，它最主要的操作就是O(lbn)的Union()，其它操作大多用这个实现的，而Fibonacci Heap是更加随意性的，更一般的堆，它是在Binomial Heap上的改进，在有时候，对某些操作非常频繁的时候，可以很好的提高效率，不过它是在平均性能上的，只有Extract_Min()和Delete()是O(lbn)的，其它操作都是O(1)，非常不错。 如果有了一个Heap，拿到n个元素，我把它们全部丢到堆中去，然后再一个一个取出来，不就排好序了吗？是的，而且排序效率在O(nlbn)的最坏情况上界。事实上这就是HeapSort的最初思想。反过来可以证明一个事实，因为n个元素在基于比较操作上的排序算法的准确上界是O(nlbn)，那么一个堆上的操作Insert()和Extract_Min()不可能同时达到比O(lbn)还低。 二叉堆的实现： #include <iostream>#include <vector>using namespace std; namespace Heap{ template <class T> class BinaryHeap {  vector<T> h;  int n; public:  BinaryHeap();  BinaryHeap(const T &err);  void max_heapify(int i);  void min_heapify(int i);  void insert(const T &e);  T minnum() const;  T extract_min();  void decrease_key(int x,const T &k);  void kill(int x); }; template <class T> BinaryHeap<T> heap_union(const BinaryHeap<T> &h1,const BinaryHeap<T> &h2);} template <class T> Heap::BinaryHeap<T>::BinaryHeap(){ h.push_back(T()); n=1;} template <class T>Heap::BinaryHeap<T>::BinaryHeap(const T &err){ h.push_back(err); n=1;} template <class T>void Heap::BinaryHeap<T>::max_heapify(int i){ //float up for(;i>1;) {  int p=i/2;  if(h[i]<h[p])  {   T temp(h[i]);   h[i]=h[p];   h[p]=temp;   i=p;  }  else   break; }} template <class T>void Heap::BinaryHeap<T>::min_heapify(int i){ //float down if(i<1 || i>=n)  return; for(;;) {  int left=i*2;  int right=left+1;  int smallest;  if(left>=n)   break;  if(right>=n)   smallest=left;  else  {   if(h[left]<h[right])    smallest=left;   else    smallest=right;  }  if(h[smallest]<h[i])  {   T temp(h[i]);   h[i]=h[smallest];   h[smallest]=temp;   i=smallest;  }  else   break; }} template <class T>void Heap::BinaryHeap<T>::insert(const T &e){ if(n>=h.size())  h.push_back(e); else  h[n]=e; n++; max_heapify(n-1);} template <class T>T Heap::BinaryHeap<T>::minnum() const{ if(n>1)  return h[1]; return h[0];} template <class T>void Heap::BinaryHeap<T>::decrease_key(int x,const T &k){ if(h[x]<k) {  //error warning  return; } h[x]=k; max_heapify(x);} template <class T>void Heap::BinaryHeap<T>::kill(int x){ if(x>=1 && x<n) {  h[x]=h[n-1];  min_heapify(x);  n--; }} template <class T>T Heap::BinaryHeap<T>::extract_min(){ if(n>1) {  T min=h[1];  kill(1);  return min; } return h[0];} int main(void){ int a[]={12,3,2,43,54,32,154,21,1}; int n=sizeof(a)/sizeof(int),i; Heap::BinaryHeap<int> bh; for(i=0;i<n;++i)  bh.insert(a[i]); for(i=0;i<n;++i)  cout<<bh.extract_min()<<endl; return 0;} 以上实现是用一个<vector>，当然你会发现在STL中是有Priority Queue的，不管那里怎么定义，这里只当是练习。 rickone 2006/11/14

评论