C++学习笔记（七）～ 优先队列（priority_queue）的简单使用

admin管理员组

文章数量:1623789

优先队列

priority_queue：优先队列，本质是堆实现。与队列不同的是，priority_queue只能访问队列头部的信息（使用top），且插入元素后，会自动排序。

基本操作:

• top(): 访问队头元素
• empty(): 队列是否为空
• size():返回队列内元素个数
• push():插入元素到队尾 (并排序)
• emplace():原地构造一个元素并插入队列
• pop():弹出队头元素
• swap():交换内容

priority_queue<Type, Container, Functional>

• Type ：数据类型，就是优先队列中每一个元素的数据类型

• Container ：容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector）【简单理解就是用什么容器实现这个优先级队列】

• Functional ：比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆【有greater、less和自定义函数，其中greater使得优先队列中的元素升序排列，所以第一个元素（头部）就是最小的元素，也就是小顶堆；less使得元素降序排列，那么第一个元素就是最大的，也就是大顶堆。】

Demo — greater()，小顶堆

#include<iostream>
#include<queue>    // 使用priority_queue只需要引入 queue 即可
using namespace std;
int main()
{
    //                      注意这里需要留一个空格 不然编译器会报错，误以为是>> 应该写成> >
    priority_queue<int,vector<int>,greater<int> > a;
    a.push(2);
    a.push(1);
	// 此时优先队列内部是： 1--2
    int temp=a.top();
    // 应该排序规则我们选的是 greater 意思是 升序排列 ， 又因为只可以访问队列头部元素
    // 所以每次访问其实就是访问的最小的那个值 是小顶堆【堆顶最小】
    cout<<"temp="<<temp<<endl;
    return 0;
}

运行结果

Demo — less()，大顶堆，【第三参数不填，默认是less】

#include<iostream>
#include<queue>
using namespace std;
int main()
{
    //                      注意这里需要留一个空格 不然编译器会报错，误以为是>> 应该写成> >
    priority_queue<int,vector<int>,less<int> > a;
    a.push(2);
    a.push(1);
    a.push(4);
    // 此时优先队列内部是： 4--2--1 
    // 因为在push操作的时候，自动会按照排序规则进行排序
    int temp=a.top();
    cout<<"temp="<<temp<<endl;
    return 0;
}

运行结果

什么情况可以使用priority_queue呢？
答：emmmm，可以想象一个场景：给你一个50人的数学成绩，你的任务就是找出前三名的成绩。 【看到这肯定觉得太简单了，先排序，再找前三就OK了，确实可以这样做，不过我们可以使用优先队列（情况复杂时，就可以体现出优先队列的好处了）】
例子：有十个同学对成绩是0、1、2。。。9分，请返回前三名的成绩。

#include<iostream>
#include<queue>
using namespace std;
int main()
{
    //初始化数组math为 0 1 2 3 。。。9
    vector<int> math;
    for(int i=0;i<10;++i)
    math.push_back(i);

    //假设我们需要返回前三名 按照第一 第二 第三的顺序
    // 思路：
    //      首先可以确定的是我们优先队列中只可以包含三个元素，即前三名的成绩
    //      那么是选用greater 还是less呢
    //      假设使用less， 那么头部元素就是最大的，而每次对优先队列访问的时候，只可以访问头部
    //      那么每次其实都是与队列中最大的值进行比较 而没有对剩余对两个数比较 难以达到要求
    //      假设使用greater 那么头部元素最小（三个中最小），每次进行比较时，都是与最小的进行比较
    //      如果该元素大于此时的最小值，那么说明此时的头部元素一定不是最终的前三名，【因为本来队列中就有两个比它大，然后又一个元素比他大，那么他肯定不是前三】
    //      所以直接pop出此时的头部元素，将该元素【比较时大的这个数】压入优先队列，至于与其他两个数的大小，我们不需要关系，因为反正我们可以确定它在前三
    //      如果此时队列的size() 【也是队列中元素的数量】小于3，那么直接将元素压入即可
    //      综上：我们选择使用 greater
    priority_queue<int,vector<int>,greater<int> > a;//定义一个优先队列a， 注意此时的写法
    for(int i=0;i<math.size();++i)
    {
        if(a.size()==3)
        {
            if(math[i]>a.top())
            {
                a.pop();
                a.push(math[i]);// 压入的时候，会自动排序
            }
        }
        else
        {
            a.push(math[i]);
        }
    }
    // 使用vector<int> ans接收答案
    vector<int> ans;
    while(!a.empty())
    {
        ans.push_back(a.top());
        a.pop();
    }
    // 因为队列此时是升序排列的：7--8--9 而我们需要的是9--8--7
    // 那么只需要对ans反序即可
    reverse(ans.begin(),ans.end());

    // 验证结果
    for(int i=0;i<ans.size();++i)
    {
        cout<<ans[i]<<endl;
    }
    return 0;
}

运行结果

自定义排序方式、使用emplace()

• 样题

swap():交换容器中的内容

测试Demo

#include<iostream>
#include<queue>
using namespace std;
int main()
{
   priority_queue<int,vector<int>,greater<int> > a;
   priority_queue<int,vector<int>,greater<int> > b;

   a.push(1);
   a.push(2);
   a.push(3);

   b.push(4);
   b.push(5);

   a.swap(b);// 使用b.swap(a)效果一样
   
   cout<<"a:"<<endl;
   while (!a.empty())
   {
       cout<<a.top()<<endl;
       a.pop();
   }
   cout<<endl;
   cout<<"b:"<<endl;
   while(!b.empty())
   {
       cout<<b.top()<<endl;
       b.pop();
   }
    return 0;
}

运行结果

本文标签： 队列学习笔记简单priorityqueue