首页 > 专题系列 > 算法分析 > C++ 优先级队列(priority_queue)
2013
12-26

C++ 优先级队列(priority_queue)

C++ 优先级队列(priority_queue)

  优先级队列顾名思义是根据元素的优先级被读取,接口和queues非常相近。程序员可以通过template参数指定一个排序准则。缺省的排序准则是利用operator< 形成降序排列,那么所谓“下一个元素”就是“数值最大的元素”。
如果同时存在若干个数值最大的元素,无法确知究竟哪一个会入选。
头文件:<queue>
在文件 <queue> 中,class priority_queue 定义如下:
namespace std {
    template < class T ,
           class Container = vector<T> ,
           class Compare = less <typename Container::value_type> >
    class priority_queue ;
}
由于priority queue需要用到STL heap算法,所以其内部容器必须支持随机存取迭代器。例如你可以使用deque来容纳元素:
std::priority_queue< float, std::deque<float> > pbuffer ;

核心接口

push() 将一个元素置于priority queue中
top()  返回priority queue中的“下一个元素”
pop() 从priority queue 中移除一个元素
注意:如果priority queue 内没有元素,执行top()和pop()会导致未定义的行为,应该先采用size()或empty()来检验容器是否为空。

运用实例

// 使用VS2008 和 code::blocks 10.05调试通过
#include <iostream>
#include <queue>
using namespace std ;

int main()
{
    priority_queue<float> q;

    // insert three elements into the priority queue
    q.push (66.6);
    q.push (22.2);
    q.push (44.4);

    // read and print two elements
    cout << q.top () << ' ';
    q.pop ();
    cout << q.top () << endl;
    q.pop ();

    // insert three more elements
    q.push (11.1);
    q.push (55.5);
    q.push (33.3);

    // skip one element
    q.pop ();

    // pop and print remaining elements
    while (!q.empty ()) {
        cout << q.top () << ' ';
        q.pop ();
    }
    cout << endl ;
}
参考资料 《C++标准程序库》侯捷 孟岩译

转自:http://www.cnblogs.com/chinazhangjie/archive/2010/10/31/1865653.html


  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的