C语言到C++STL菜鸟教程：Priority_queue(优先队列)

2022-07-1712:50:32编程语言入门到精通Comments1,418 views字数 2157阅读模式

1. 简介文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

优先队列是一种极其特殊的队列，他与标准的队列使用线性结构进行计算不同，优先队列的底层是以散列的状态（非线性）表现的，他与标准的队列有如下的区别，标准的队列遵从严格的先进先出，优先队列并不遵从标准的先进先出，而是对每一个数据赋予一个权值，根据当前队列权值的状态进行排序，使得权值最大（或最小）的永远排在队列的最前面。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

2. 相关文件文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

由于其属于队列的一种，因此可以直接使用队列的头文件#include<queue>文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

3. 初始化文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

priority_queue<T, Container, Compare>
priority_queue<T>        //直接输入元素则使用默认容器和比较函数

与往常的初始化不同，优先队列的初始化涉及到一组而外的变量，这里解释一下初始化：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

a) T就是Type为数据类型文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

b) Container是容器类型，（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector）文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

c) Compare是比较方法，类似于sort第三个参数那样的比较方式，对于自定义类型，需要我们手动进行比较运算符的重载。与sort直接Bool一个函数来进行比较的简单方法不同，Compare需要使用结构体的运算符重载完成，直接bool cmp(int a,int b){  return a>b; } 这么写是无法通过编译的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

使用的举例有：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

struct cmp
{ //这个比较要用结构体表示
    bool operator()(int &a, int &b) const
    {
        return a > b;
    }
};
 
priority_queue<int,vector<int>,cmp> q;    //使用自定义比较方法
priority_queue<int> pq;

4. 常用接口文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

我们预先通过priority_queue <int> q创建了一个队列，命名为q，方便举例。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

a)大小size()文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

返回队列元素的个数文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

函数原型：size_type size() const;文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

cout<<q.size()<<endl;   //直接返回队列中元素的个数

b) 入队push()文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

进行入队操作，在队尾处进行插入文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

函数原型：void push (const value_type& val);文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

q.push(100);

c) 出队pop()文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

进行出队操作，在对头出进行弹出文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

函数原型：void pop();文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

q.pop();

d) 访问队头元素top()文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

与标准队列不同，优先队列只允许访问队头元素，不允许访问其余的数据，由于堆的特殊性质，堆顶元素的优先权最高（或者最低），访问其余元素没有意义，因此，优先队列只允许访问队头元素，这和栈的访问类型类似所以使用栈访问栈顶的命名top文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

函数原型是：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

reference& top();文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

const_reference& top() const;文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

 cout<<q.top()<<endl;

e) 判空empty()文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

返回一个bool类型的值，只存在真和假，当队列为空时为真，不为空时为假文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

函数原型文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

bool empty() const;文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

可以利用empty()进行队列的遍历操作，这里建议先使用初始化函数将队列进行复制，否则遍历之后队列就为空了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

  while(q.empty()){
        cout<<q.pop()<<endl;
        q.pop();
    }

5.实例代码文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

可以通过这个代码进行参考，可以看的输出的结果是顺序的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

#include <queue>
#include <iostream>
using namespace std;
struct cmp
{ //这个比较要用结构体表示
    bool operator()(int &a, int &b) const
    {
        return a > b;
    }
};
int main()
{
    priority_queue<int, vector<int>, cmp> q;
    for (int i = 1; i <= 5; i++)
    {
        q.push(i * 10);
        cout << "push element " << i << endl;
    }
    q.push(15);
    q.push(4);
    int i = 1;
    while (!q.empty())
    {
        int temp = q.top();
        q.pop();
        cout << "No " << i++ << " element is: " << temp << endl;
    }
    return 0;
}

输出：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html

push element 1
push element 2
push element 3
push element 4
push element 5
No 1 element is: 4
No 2 element is: 10
No 3 element is: 15
No 4 element is: 20
No 5 element is: 30
No 6 element is: 40
No 7 element is: 50
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/25122.html
  • 本站内容整理自互联网，仅提供信息存储空间服务，以方便学习之用。如对文章、图片、字体等版权有疑问，请在下方留言，管理员看到后，将第一时间进行处理。
  • 转载请务必保留本文链接：https://www.cainiaoxueyuan.com/ymba/25122.html

Comment

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定