STL priority_queue 优先级队列

时间：2022-06-13 14:38:42

http://www.cplusplus.com/reference/queue/priority_queue/

在STL里有这个priority_queue，实现优先队列的结构。在优先队列中，优先级高的元素先出队列。
现在在这里说说用法吧

其实就三种用法

第一种，直接使用默认的。

它的模板声明带有三个参数，priority_queue<Type, Container, Functional>
Type 为数据类型， Container 为保存数据的容器，Functional 为元素比较方式。
Container 必须是用数组实现的容器，比如 vector, deque 但不能用 list.
STL里面默认用的是 vector. 比较方式默认用 operator< , 所以如果你把后面俩个
参数缺省的话，优先队列就是大顶堆，队头元素最大。
看例子


priority_queue<int> qi;

    int a[len] = {3,5,9,6,2};

    priority_queue<int> qi;
    for(i = 0; i < len; i++)
        qi.push(a[i]);

    for(i = 0; i < len; i++)
    {
        cout<<qi.top()<<" ";
        qi.pop();
    }

通过<操作符可知在整数中元素大的优先级高。
故例子中输出结果为：9 6 5 3 2


第二种方法：
在示例1中，如果我们要把元素从小到大输出怎么办呢？
这时我们可以传入一个比较函数，使用functional.h函数对象作为比较函数。

如果要用到小顶堆，则一般要把模板的三个参数都带进去。
STL里面定义了一个仿函数 greater<>，对于基本类型可以用这个仿函数声明小顶堆
priority_queue<int, vector<int>, greater<int> >qi2;

对于自定义类型，则必须自己重载 operator< 或者自己写仿函数

#include <iostream>
#include <queue>

using namespace std;

struct Node{
    int x, y;
    Node( int a= 0, int b= 0 ):
        x(a), y(b) {}
};

bool operator<( Node a, Node b ){
    if( a.x== b.x ) return a.y> b.y;                //多关键字排序     > 表示升序，关键字小的优先级高

    return a.x> b.x;
}

如何理解return a1>a2 表示升序，<表示降序？

例如: return a1>a2

可理解成:

                   如果a1>a2,返回true，则元素交换位置，故最终得到的是升序结果。否则返回false，不交换

                 

int main(){
    priority_queue<Node> q;
   
    for( int i= 0; i< 10; ++i )
    q.push( Node( rand(), rand() ) );
   
    while( !q.empty() ){
        cout << q.top().x << ' ' << q.top().y << endl;
        q.pop();
    }
   
    getchar();
    return 0;
}

或者这样定义也是能达到效果的：

struct Node{
    int x, y;
    Node( int a= 0, int b= 0 ):
        x(a), y(b) {}

    friend operator<( Node a, Node b ){
    if( a.x== b.x ) return a.y> b.y;
    return a.x> b.x;

    }
};

自定义类型重载 operator< 后，声明对象时就可以只带一个模板参数。
但此时不能像基本类型这样声明
priority_queue<Node, vector<Node>, greater<Node> >;
原因是 greater<Node> 没有定义，如果想用这种方法定义
则可以按如下方式

例子:

#include <iostream>
#include <queue>

using namespace std;

struct Node{
    int x, y;
    Node( int a= 0, int b= 0 ):
        x(a), y(b) {}
};

struct cmp{
    bool operator() ( Node a, Node b ){
        if( a.x== b.x ) return a.y> b.y;
       
        return a.x> b.x; }
};

int main(){
    priority_queue<Node, vector<Node>, cmp> q;
   
    for( int i= 0; i< 10; ++i )
    q.push( Node( rand(), rand() ) );
   
    while( !q.empty() ){
        cout << q.top().x << ' ' << q.top().y << endl;
        q.pop();
    }
   
    getchar();
    return 0;
}

还有一点要注意的是priority_queue中的三个参数，后两个可以省去，因为有默认参数，不过如果，有第三个参数的话，必定要写第二个参数。

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的函数列表是相同的。

 

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

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

 

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

 http://www.cnblogs.com/mfryf/archive/2012/09/05/2671883.html


标签：

相关文章