优先队列priority_queue的使用方法

以下内容摘自http://blog.csdn.net/morewindows/article/details/6976468

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

3.png

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

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

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

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

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

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

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

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

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

简单来说,优先队列有如下使用方法
构建一个 内置类型 /具有operator < 的优先队列

priority_queue Queue;

其中Type必须有operator <, 否则将引起编译错误。另外,如果以成员函数重载operator <,需要注意this与传入相同的问题。友元重载就没有这个问题。

构建一个 自定义算法的 优先队列

priority_queue<Type,vector,TypeCmp> Queue;

其中vector是优先队列内部使用的容器,建议使用vector. TypeCmp是一个类(或结构体)重载()形成仿函数形式

struct TypeCmp

{

bool operator() (const Type& a,const Type& b);

};

如果TypeCmp()调用了Type的私有数据域,那么Type的定义中相应的应该加上friend TypeCmp;

(由于仿函数和lambda的相似性我又写了个lambda然而编译失败了….)

另外,优先队列的排序方法与实际结果正好是相反的,这一点需要注意。

文章转自: https://blog.csdn.net/Kiritow/article/details/51451574

文章作者: QUST-Coder
文章链接: http://qustkx.com/2019/08/17/blog8/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 青岛科技大学信息学院科技创新协会