STL-priority_queue用法（重点: 升序，小根堆）

面，总结一下priority_queue的用法，免得以后又忘记了，还要到处找（C++的STL的库，异常处理、多态、泛型编程，自己还要多积累才是。）

#include <queue>

using namespace std; (记得包含头文件噢)

1.  priority_queue在STL内部定义的原型是：

      template< class T ,

                     class Sequence=vector<T> ,

                     classCompare=less<typename Sequence::value_type> > （主要，要一个空格，否则编译器会当做右移操作符，报错）

                     class priority_queue;

最简单的用法:

priority_queue<int>  q;   // 注意上面第二个参数，和第三个参数的默认值。

                                   // 对于内置的对象，可以这么简单的定义；特别注意第三个参数, 默认的小于号（<）, 即降序排序，默认的是大根堆。权值最大的会被弹出来。

 最常见的用法：

priority_queue<Node> q;   // 恩，自己定义的类型。

----------上面两种类型，当自己需要的堆是小根堆的时候，即元素按升序（从小到达的弹出），那么必须改写比较函数.

即对于STL中优先队列的使用，最重要的就是这个比较函数的书写（或对'<', '>'的重载）了，常见的方面有下面两种：

1. 方法一，重载'<' ('>')运算符：

2. 方法二，构造‘比较函数’，然后指定priority_queue的第三个参数

struct cmp

{

       bool operator() (const Node& a, const Node &b)

        {

                return a.key > b.key;      // 第一个元素大于第二个元素，返回真时； 对应的是小根堆，升序！

        }                                         // 当想要大根堆，降序时，让它返回false就好，即用'<' (默认值)

}

多关键字比较、'排序':

struct cmp {
     bool operator() (const node &a, const node &b)
     {
         if (a.current < b.current)    return false;     //第一关键字，为升序，小根堆  (第一个大于第二的时候，返回真)
         else if (a.current == b.current)   return (a.year > b.year);   // 第二关键字，也为升序
         else return true;
     }
};

priority_queue<node, vector<node>, cmp> p;

-----------其实这两种方法，很常见。使用STL的algorithm里的sort等算法时，都需要指定！

2. 对于优先队列使用时，特别是多个case的时候，要注意初始的清空!

while ( !q.empty() )  q.pop();    //效率不高？为什么没有提供clear的功能噢。

 q.push( cur );   q.top();   q.pop();  q.size();

恩，对于，对于STL中优先队列的时候应该没问题了。主要两点:  1. 比较函数或运算符的重载  2. 注意case之间的清空!

本文转自博客园知识天地的博客，原文链接：STL-priority_queue用法（重点: 升序，小根堆），如需转载请自行联系原博主。