首页 > 代码库 > priority_queue 优先级队列

priority_queue 优先级队列

2024-10-04 19:31:39   217人阅读

priority_queue 优先级队列是一个拥有权值概念的单向队列queue，在这个队列中，所有元素是按优先级排列的（也可以认为queue是个按进入队列的先后做为优先级的优先级队列——先进入队列的元素优先权要高于后进入队列的元素）。在计算机操作系统中，优先级队列的使用是相当频繁的，进线程调度都会用到。在STL的具体实现中，priority_queue也是以别的容器作为底部结构，再根据堆的处理规则来调整元素之间的位置。下面给出priority_queue的函数列表和VS2008中priority_queue的源代码，本文中与heap有关的函数参见《STL系列之四 heap 堆》。

priority_queue函数列表
函数描述      by MoreWindows( http://blog.csdn.net/MoreWindows )
构造析构
 
priority_queue <Elem> c
 创建一个空的queue 。
注：priority_queue构造函数有7个版本，请查阅MSDN
数据访问与增减
 
c.top()返回队列头部数据
c.push(elem)在队列尾部增加elem数据
 c.pop()队列头部数据出队
其它操作
 
c.empty()判断队列是否为空
c.size()

返回队列中数据的个数

  

可以看出priority_queue的函数列表与栈stack的函数列表是相同的。

 

VS2008中priority_queue 优先级队列的源代码

友情提示：初次阅读时请注意其实现思想，不要在细节上浪费过多的时间

 

[cpp] view plain copy
 
  1. //VS2008中 priority_queue的定义 MoreWindows整理( http://blog.csdn.net/MoreWindows )  
  2. template<class _Ty, class _Container = vector<_Ty>, class _Pr = less<typename _Container::value_type> > //默认以vector为容器的  
  3. class priority_queue  
  4. {   // priority queue implemented with a _Container  
  5. public:  
  6.     typedef _Container container_type;  
  7.     typedef typename _Container::value_type value_type;  
  8.     typedef typename _Container::size_type size_type;  
  9.     typedef typename _Container::reference reference;  
  10.     typedef typename _Container::const_reference const_reference;  
  11.   
  12.     priority_queue() : c(), comp()  
  13.     {   // construct with empty container, default comparator  
  14.     }  
  15.   
  16.     explicit priority_queue(const _Pr& _Pred) : c(), comp(_Pred)  
  17.     {   // construct with empty container, specified comparator  
  18.     }  
  19.   
  20.     priority_queue(const _Pr& _Pred, const _Container& _Cont) : c(_Cont), comp(_Pred)  
  21.     {   // construct by copying specified container, comparator  
  22.         make_heap(c.begin(), c.end(), comp); //参见《STL系列之四 heap 堆的相关函数》  
  23.     }  
  24.   
  25.     template<class _Iter>  
  26.     priority_queue(_Iter _First, _Iter _Last) : c(_First, _Last), comp()  
  27.     {   // construct by copying [_First, _Last), default comparator  
  28.         make_heap(c.begin(), c.end(), comp);  
  29.     }  
  30.   
  31.     template<class _Iter>  
  32.     priority_queue(_Iter _First, _Iter _Last, const _Pr& _Pred) : c(_First, _Last), comp(_Pred)  
  33.     {   // construct by copying [_First, _Last), specified comparator  
  34.         make_heap(c.begin(), c.end(), comp);  
  35.     }  
  36.   
  37.     template<class _Iter>  
  38.     priority_queue(_Iter _First, _Iter _Last, const _Pr& _Pred, const _Container& _Cont) : c(_Cont), comp(_Pred)  
  39.     {   // construct by copying [_First, _Last), container, and comparator  
  40.         c.insert(c.end(), _First, _Last);  
  41.         make_heap(c.begin(), c.end(), comp);  
  42.     }  
  43.   
  44.     bool empty() const  
  45.     {   // test if queue is empty  
  46.         return (c.empty());  
  47.     }  
  48.   
  49.     size_type size() const  
  50.     {   // return length of queue  
  51.         return (c.size());  
  52.     }  
  53.   
  54.     const_reference top() const  
  55.     {   // return highest-priority element  
  56.         return (c.front());  
  57.     }  
  58.   
  59.     reference top()  
  60.     {   // return mutable highest-priority element (retained)  
  61.         return (c.front());  
  62.     }  
  63.   
  64.     void push(const value_type& _Pred)  
  65.     {   // insert value in priority order  
  66.         c.push_back(_Pred);  
  67.         push_heap(c.begin(), c.end(), comp);  
  68.     }  
  69.   
  70.     void pop()  
  71.     {   // erase highest-priority element  
  72.         pop_heap(c.begin(), c.end(), comp);  
  73.         c.pop_back();  
  74.     }  
  75.   
  76. protected:  
  77.     _Container c;   // the underlying container  
  78.     _Pr comp;   // the comparator functor  
  79. };  

下面先给出优级先级队列的使用范例。

[cpp] view plain copy
 
  1. //优先级队列 priority_queue by MoreWindows( http://blog.csdn.net/MoreWindows )  
  2. // 支持 empty() size() top() push() pop() 与stack的操作函数全部一样  
  3. //by MoreWindows  
  4. #include <queue>  
  5. #include <list>  
  6. #include <cstdio>  
  7. using namespace std;  
  8. int main()  
  9. {  
  10.     //优先级队列默认是使用vector作容器。  
  11.     priority_queue<int> a;  
  12.     priority_queue<int, list<int>> b; //可以这样声明，但无法使用  
  13.     int i;  
  14.     //压入数据  
  15.     for (i = 0; i < 10; i++)  
  16.     {  
  17.         a.push(i * 2 - 5);  
  18.         //b.push(i); //编译错误  
  19.     }  
  20.     //优先级队列的大小  
  21.     printf("%d\n", a.size());  
  22.     //取优先级队列数据并将数据移出队列  
  23.     while (!a.empty())  
  24.     {  
  25.         printf("%d ", a.top());  
  26.         a.pop();  
  27.     }  
  28.     putchar(‘\n‘);  
  29.     return 0;  
  30. }  

下面程序是针对结构体的，对数据的比较是通过对结构体重载operator()。

程序功能是模拟排队过程，每人有姓名和优先级，优先级相同则比较姓名，开始有5个人进入队列，然后队头2个人出队，再有3个人进入队列，最后所有人都依次出队，程序会输出离开队伍的顺序。

[cpp] view plain copy
 
  1. //by MoreWindows( http://blog.csdn.net/MoreWindows )  
  2. #include <queue>  
  3. #include <cstring>  
  4. #include <cstdio>  
  5. using namespace std;  
  6. //结构体  
  7. struct Node  
  8. {  
  9.     char szName[20];  
  10.     int  priority;  
  11.     Node(int nri, char *pszName)  
  12.     {  
  13.         strcpy(szName, pszName);  
  14.         priority = nri;  
  15.     }  
  16. };  
  17. //结构体的比较方法 改写operator()  
  18. struct NodeCmp  
  19. {  
  20.     bool operator()(const Node &na, const Node &nb)  
  21.     {  
  22.         if (na.priority != nb.priority)  
  23.             return na.priority <= nb.priority;  
  24.         else  
  25.             return strcmp(na.szName, nb.szName) > 0;  
  26.     }  
  27. };  
  28. void PrintfNode(Node &na)  
  29. {  
  30.     printf("%s %d\n", na.szName, na.priority);  
  31. }  
  32. int main()  
  33. {  
  34.     //优先级队列默认是使用vector作容器，底层数据结构为堆。  
  35.     priority_queue<Node, vector<Node>, NodeCmp> a;  
  36.   
  37.     //有5个人进入队列  
  38.     a.push(Node(5, "小谭"));  
  39.     a.push(Node(3, "小刘"));  
  40.     a.push(Node(1, "小涛"));  
  41.     a.push(Node(5, "小王"));  
  42.   
  43.     //队头的2个人出队  
  44.     PrintfNode(a.top());  
  45.     a.pop();  
  46.     PrintfNode(a.top());  
  47.     a.pop();  
  48.     printf("--------------------\n");  
  49.   
  50.     //再进入3个人  
  51.     a.push(Node(2, "小白"));  
  52.     a.push(Node(2, "小强"));  
  53.     a.push(Node(3, "小新"));  
  54.   
  55.     //所有人都依次出队  
  56.     while (!a.empty())  
  57.     {  
  58.         PrintfNode(a.top());  
  59.         a.pop();  
  60.     }  
  61.   
  62.     return 0;  
  63. }  

priority_queue 优先级队列


联系
我们