标题：Priority Queue - Binary Heap
出处：Felix021
时间：Thu, 14 Aug 2008 02:51:06 +0000
作者：felix021
地址：https://www.felix021.com/blog/read.php?1084

内容：
from http://www.programfan.com/blog/article.asp?id=20319

没什么好写的，都在《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


引用地址：http://blog.programfan.com/trackback.asp?id=20319



Generated by Bo-blog 2.1.0