Aug 14

Priority Queue - Binary Heap 不指定

felix021 @ 2008-8-14 02:51 [IT » 程序设计] 评论(0) , 引用(0) , 阅读(3091) | Via 本站原创 | |
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




欢迎扫码关注:




转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php
发表评论
表情
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
打开HTML
打开UBB
打开表情
隐藏
记住我
昵称   密码   *非必须
网址   电邮   [注册]