STL系列之五 priority_queue 优先级队列

迷南。 2022-09-18 12:49 146阅读 0赞

原文地址：

[http://blog.csdn.net/morewindows/article/details/6976468][http_blog.csdn.net_morewindows_article_details_6976468]

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

<table style="color:rgb(51,51,51); font-family:Arial; font-size:14px; line-height:26px; width:668px; height:245px"> priority_queue函数列表 
 <tbody> 
 <tr> 
 <td>函数</td> 
 <td>描述&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;by&nbsp;MoreWindows(&nbsp;<a href="http://blog.csdn.net/MoreWindows" style="color:rgb(51,102,153); text-decoration:none" rel="nofollow">http://blog.csdn.net/MoreWindows</a>&nbsp;)</td> 
 </tr> 
 <tr> 
 <td>构造析构 </td> 
 <td></td> 
 </tr> 
 <tr> 
 <td>priority_queue &lt;Elem&gt; c </td> 
 <td>&nbsp;创建一个空的queue 。 注：priority_queue构造函数有7个版本，请查阅MSDN </td> 
 </tr> 
 <tr> 
 <td>数据访问与增减 </td> 
 <td></td> 
 </tr> 
 <tr> 
 <td>c.top()</td> 
 <td>返回队列头部数据 </td> 
 </tr> 
 <tr> 
 <td>c.push(elem)</td> 
 <td>在队列尾部增加elem数据 </td> 
 </tr> 
 <tr> 
 <td>&nbsp;c.pop()</td> 
 <td>队列头部数据出队 </td> 
 </tr> 
 <tr> 
 <td>其它操作 </td> 
 <td></td> 
 </tr> 
 <tr> 
 <td>c.empty()</td> 
 <td>判断队列是否为空</td> 
 </tr> 
 <tr> 
 <td>c.size()</td> 
 <td> 返回队列中数据的个数 </td> 
 </tr> 
 <tr> 
 <td>&nbsp;</td> 
 <td></td> 
 </tr> 
 </tbody> 
</table>

可以看出priority\_queue的函数列表与栈[stack][]的函数列表是相同的。

**VS2008中priority\_queue 优先级队列的源代码**

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

**\[cpp\]**  [view plain][] [copy][view plain]

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][view plain]

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][view plain]

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. \}

读者可以将上面结构体Node改成类来试下，答案2天后发到本篇的评论中。

转载请标明出处，原文地址：[http://blog.csdn.net/morewindows/article/details/6976468][http_blog.csdn.net_morewindows_article_details_6976468]

[http_blog.csdn.net_morewindows_article_details_6976468]: http://blog.csdn.net/morewindows/article/details/6976468
[queue]: http://blog.csdn.net/morewindows/article/details/6950917
[STL_ heap]: http://blog.csdn.net/morewindows/article/details/6967409
[stack]: http://blog.csdn.net/morewindows/article/details/6950881
[view plain]: http://blog.csdn.net/morewindows/article/details/6976468#