优先队列

优先队列可以从尾部插入元素，然后从头部取出优先级（通过一个数值表示）最高的对象。这种支持插入，然后每次仅仅取出一个对象数据结构，完全天然和堆一一对应，所以通过堆实现优先队列适配器是天然的选择。也就是说最大堆其实就是优先队列。优先队列没有迭代器，进出都有一定的规则，只有queue顶端的元素（权重最高者），才有机会被外界取用。

STL源码

#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
template <class T, class Sequence = vector<T>, class Compare = less<typename Sequence::value_type> >
#else
template <class T, class Sequence, class Compare>
#endif
class  priority_queue {
public:typedef typename Sequence::value_type value_type;typedef typename Sequence::size_type size_type;typedef typename Sequence::reference reference;typedef typename Sequence::const_reference const_reference;
protected:Sequence c;Compare comp;
public:priority_queue() : c() {}explicit priority_queue(const Compare& x) :  c(), comp(x) {}#ifdef __STL_MEMBER_TEMPLATEStemplate <class InputIterator>priority_queue(InputIterator first, InputIterator last, const Compare& x): c(first, last), comp(x) { make_heap(c.begin(), c.end(), comp); }template <class InputIterator>priority_queue(InputIterator first, InputIterator last) : c(first, last) { make_heap(c.begin(), c.end(), comp); }
#else /* __STL_MEMBER_TEMPLATES */priority_queue(const value_type* first, const value_type* last, const Compare& x) : c(first, last), comp(x) {make_heap(c.begin(), c.end(), comp);}priority_queue(const value_type* first, const value_type* last) : c(first, last) { make_heap(c.begin(), c.end(), comp); }//将元素优先级比较
#endif /* __STL_MEMBER_TEMPLATES */bool empty() const { return c.empty(); }size_type size() const { return c.size(); }const_reference top() const { return c.front(); }void push(const value_type& x) {//实际就是插入，然后push_heap__STL_TRY {c.push_back(x); push_heap(c.begin(), c.end(), comp);}__STL_UNWIND(c.clear());}void pop() {//实际就是pop_heap，然后弹出外部元素__STL_TRY {pop_heap(c.begin(), c.end(), comp);c.pop_back();}__STL_UNWIND(c.clear());}
};

使用例子

#include <iostream>
#include <list>
#include <algorithm>
#include <iterator>
#include <deque>
#include <queue>
#include <algorithm>
#include <stdio.h>
#include <string>
using namespace std;
class Course{
public:Course(){}Course(const string &n , const int &pri):name(n) , priority(pri){}bool operator<(const Course& x) const{return priority < x.priority;}string name;int priority;
};int main()
{Course Course1("math" , 5);Course Course2("english" ,   4);Course Course3("chinese" ,   3 );Course Course4("history" ,   2);Course Course5("chemistry" , 1);priority_queue<Course> pri_que;pri_que.push(Course5);pri_que.push(Course4);pri_que.push(Course3);pri_que.push(Course2);pri_que.push(Course1);while(!pri_que.empty()){std::cout << pri_que.top().name << endl;//取出优先级最高pri_que.pop();//然后谈出元素}

注意：先top读取，然后pop删除优先队列顶的元素。实际上是通过堆操作的，上述重要的就是重载<运算符，使得两个科目对象可以比较。