开发者社区> 流楚丶格念> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

C++优先队列(priority_queue)用法详解

简介: C++优先队列(priority_queue)用法详解
+关注继续查看

priority_queue


对于这个模板类priority_queue,它是STL所提供的一个非常有效的容器。


作为队列的一个延伸,优先队列包含在头文件 <queue> 中。


优先队列介绍


优先队列是一种比较重要的数据结构,它是有二项队列编写而成的,可以以O(log n) 的效率查找一个队列中的最大值或者最小值,其中是最大值还是最小值是根据创建的优先队列的性质来决定的。


模板 参数


优先队列有三个参数,其声明形式为:


priority_queue< type, container, function >


这三个参数,后面两个可以省略,第一个不可以。


其中:


  • type:数据类型;


  • container:实现优先队列的底层容器;


  • function:元素之间的比较方式;


对于container,要求必须是数组形式实现的容器,例如vector、deque,而不能使list。


在STL中,默认情况下(不加后面两个参数)是以vector为容器,以 operator< 为比较方式,所以在只使用第一个参数时,优先队列默认是一个最大堆,每次输出的堆顶元素是此时堆中的最大元素。


priority_queue成员函数


假设type类型为int,则:


  • bool empty() const


返回值为true,说明队列为空;


  • int size() const


返回优先队列中元素的数量;


  • void pop()


删除队列顶部的元素,也即根节点


  • int top()


返回队列中的顶部元素,但不删除该元素;


  • void push(int arg)


将元素arg插入到队列之中;


大顶堆与小顶堆


大顶堆(降序)


//构造一个空的优先队列(此优先队列默认为大顶堆)
priority_queue<int> big_heap;   

//另一种构建大顶堆的方法
priority_queue<int,vector<int>,less<int> > big_heap2;   


小顶堆(升序)


//构造一个空的优先队列,此优先队列是一个小顶堆
priority_queue<int,vector<int>,greater<int> > small_heap;


注意事项


需要注意的是,如果使用less和greater,需要头文件:


#include <functional>


代码案例


image


#include<iostream>
#include <queue>
#include<string>
#include<string.h>
using namespace std;
int main()
{
    //对于基础类型 默认是大顶堆
    priority_queue<int> a;
    //等同于 priority_queue<int, vector<int>, less<int> > a;

    // 这样就是小顶堆
    // 好习惯  >>中间要加空格 
    priority_queue<int, vector<int>, greater<int> > c;
    priority_queue<string> b;

    for (int i = 0; i < 5; i++)
    {
        a.push(i);
        c.push(i);
    }

    // 降序输出
    while (!a.empty())
    {
        cout << a.top() << ' ';
        a.pop();
    }
    cout << endl;

    // 升序输出
    while (!c.empty())
    {
        cout << c.top() << ' ';
        c.pop();
    }
    cout << endl;

    b.push("abc");
    b.push("abcd");
    b.push("cbd");
    while (!b.empty())
    {
        cout << b.top() << ' ';
        b.pop();
    }
    cout << endl;
    return 0;
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
【C++】优先级队列 priority_queue的使用及模拟实现@STL —— 仿函数
优先级队列也是一种容器适配器,默认情况下它适配的是vector,以支持堆的算法中频繁的随机访问。priority_queue不像stack & queue的适配只是简单复用,还搭配了堆的算法。那么,如何控制大堆还是小堆呢?就要通过简单的**仿函数**啦。let's go!
8 0
【C++初阶学习】stack/queue/priority_queue的使用和模拟(1)
【C++初阶学习】stack/queue/priority_queue的使用和模拟(1)
32 0
标准模板库(STL)学习指南之priority_queue优先队列
转载自CSDN博客:http://blog.csdn.net/suwei19870312/article/details/5294016 priority_queue 调用 STL里面的 make_heap(), pop_heap(), push_heap() 算法实现,也算是堆的另外一种形式。
748 0
标准模板库(STL)学习指南之priority_queue优先队列
转载自CSDN博客:http://blog.csdn.net/suwei19870312/article/details/5294016 priority_queue 调用 STL里面的 make_heap(), pop_heap(), push_heap() 算法实现,也算是堆的另外一种形式。
761 0
Queue 队列的用法
队列是一种特殊的线性表,它只允许在表的前端进行删除操作,而在表的后端进行插入操作。 LinkedList类实现了Queue接口,因此我们可以把LinkedList当成Queue来用。 以下实例演示了队列(Queue)的用法: import java.
856 0
STL之priority_queue为复合结构排序
priority_queue为复合结构排序:  1 #include 2 #include 3 4 using namespace std; 5 struct Node{ 6 int x; 7 string y; 8 Node(...
726 0
deque queue and priority_queue
deque queue and priority_queue stl-deque deque 是双端队列,可实现栈与队列的操作。 deque支持deque_ob[i] 形式的随机存取。 stl-queue queue的基本操作有: 入队,如例:q.push(x); 将x 接到队列的末端。 出队,如例:q.pop(); 弹出队列的第一个元素,注意,并不会返回被弹出元素
1110 0
STL队列 之FIFO队列(queue)、优先队列(priority_queue)、双端队列(deque)
1.FIFO队列     std::queue就是普通意思上的FIFO队列在STL中的模版。   1.1主要的方法有:     (1)T front():访问队列的对头元素,并不删除对头元素     (2)T back():访问队列的末尾元素,并不删除末尾元素     (3)void pop():删除对头元素。
967 0
纸上谈兵: 队列 (queue)
作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢!   队列(queue)是一个简单而常见的数据结构。队列也是有序的元素集合。
736 0
+关注
流楚丶格念
csdn平台优质创作者,51cto TOP博主,360图书馆科技博主,燕山大学目前大三在读,日拱一卒,功不唐捐,加油!!!
1010
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载