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

这篇具有很好参考价值的文章主要介绍了C++优先队列(priority_queue)详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一、 定义

二、优先队列内元素访问

三、优先队列常用函数

四、优先队列内元素的优先级


         优先队列(priority_queue),底层的数据结构为堆(heap),以此保证队首元素一定是当前队列所有元素中优先级最高的。我们也可以随时往优先队里面加入(push)元素,其队首元素依然为优先级最高的。

一、 定义

        头文件:#include<queue>

        定义的写法与其他STL容器相同,Type可以是任意的基本数据类型或是容器,Container是容器类型(这里必须是用数组实现的容器,例如vector,deque,但是不能使用list,STL里默认是vector),Functional是比较方式(升序队列:大顶堆;降序队列:小顶堆):

priority_queue<Type,Container,Functional> name;

二、优先队列内元素访问

        普通队列是先进先出的数据结构,元素在队尾添加,在队头删除。

        在优先队列中,当访问元素时,元素被赋以优先级,优先级高的元素先删除,先出队。

        优先队列与普通队列的不同在于我们可以定义队列内元素的优先级,通过优先级控制出队顺序。优先队列没有front()函数和back()函数只能通过top()函数来访问队首元素(即堆顶元素):

#include<iostream>
#include<queue>
using namespace std;
int main()
{
    priority_queue<int> pot;
    pot.push(2);
    pot.push(6);
    pot.push(3);
    cout << pot.top() << endl;
    return 0;
} 

输出结果:6

三、优先队列常用函数

        与队列基本操作大致相同:

  • push()           插入元素到队尾并排序,时间复杂度为O(logN)
  • top()              访问队首元素,时间复杂度为O(1),使用前应先判断优先队列是否为空
  • pop               弹出队首元素,时间复杂度为O(logN),使用前应先判断优先队列是否为空
  • empty()         判断队列是否为空,时间复杂度为O(1)
  • size()             返回队内元素个数,时间复杂度为O(1)
  • emplace()      原地构造一个元素并插入队列 
  • swap()           交换内容
#include<iostream>
#include<queue>
using namespace std;
int main()
{
    priority_queue<int> dsp;
    //判断优先队列是否为空
    cout << dsp.empty() << endl;
    dsp.push(2);
    dsp.push(4);
    dsp.push(1);
    dsp.push(5);
    //输出队首元素
    cout << dsp.top() << endl;
    //弹出队首元素,再输出队顶元素
    dsp.pop();
    cout << dsp.top() << endl;
    //输出优先队列元素个数
    cout << dsp.size() << endl;
}

 输出结果:

c++优先队列,c++,数据结构,开发语言

四、优先队列内元素的优先级

        像int、double、char等基本数据类型,他们的优先级一般就是数字较大的优先级较高(如果是char型的就是根据字典序大小):

priority_queue<int> dsp;
priority_queue<int, vector<int>, less<int> > dsp;
priority_queue<int, vector<int>, greater<int> > dsp;

        第一种即常见的定义方法,后面两种中多了两个参数,vector<>是用来承载底层堆结构的容器;less<>和greater<>则是第一个参数的比较类,分别表示数字越大优先级越大(大顶堆)、数字越小优先级越高(小顶堆)。文章来源地址https://www.toymoban.com/news/detail-567082.html

到了这里,关于C++优先队列(priority_queue)详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 『C++ - STL』之优先级队列( priority_queue )

    什么是优先级队列,从该名中可以知道他一定有队列的一定属性,即先入先出(LILO),而这里的优先级则可以判断出它的另一个特点就是可以按照一定的条件将符合该条件的先进行出队,这就是优先级队列; 而在数据结构中有一个支持该操作的结构 - 堆( heap ); 而在STL中,这个

    2024年02月07日
    浏览(45)
  • 【C++初阶】模拟实现优先级队列priority_queue

    👦个人主页:@Weraphael ✍🏻作者简介:目前学习C++和算法 ✈️专栏:C++航路 🐋 希望大家多多支持,咱一起进步!😁 如果文章对你有帮助的话 欢迎 评论💬 点赞👍🏻 收藏 📂 加关注✨ 优先级队列顾名思义就是 按优先级出队列 priority_queue 是一个容器适配器,默认使用

    2024年02月10日
    浏览(40)
  • 【C++入门到精通】C++入门 —— priority_queue(STL)优先队列

    ⭕文章绑定了VS平台下std::priority_queue的源码,大家可以下载了解一下😍 前面我们讲了C语言的基础知识,也了解了一些数据结构,并且讲了有关C++的命名空间的一些知识点以及关于C++的缺省参数、函数重载,引用 和 内联函数也认识了什么是类和对象以及怎么去new一个 ‘对象

    2024年02月12日
    浏览(48)
  • C++——优先级队列(priority_queue)的使用及实现

    目录 一.priority_queue的使用 1.1、基本介绍 1.2、优先级队列的定义 1.3、基本操作(常见接口的使用) 1.4、重写仿函数支持自定义数据类型 二.priority_queue的模拟实现 2.1、构造重要的调整算法 2.2、常见接口的实现 push() pop() top() empty()、size()  三.利用仿函数改进调整算法 我们之前

    2024年02月02日
    浏览(43)
  • 【C++】——栈和队列(stack、queue)及优先队列(priority_queue)的介绍和模拟实现

    今天我们来学习C++stl六大组件的其中一种,容器适配器,stack、queue及priority_queue都是容器适配器。我们循序渐进,接下来让我们先认识一下什么是容器适配器。 适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结),该

    2024年02月08日
    浏览(51)
  • 【C++】STL使用仿函数控制优先级队列priority_queue

    本文章讲解C++STL的容器适配器:priority_queue的实现,并实现仿函数控制priority_queue底层。 priority_queue叫做优先级队列,它的底层结构是堆,在库中,默认生成的是大堆 在库的实现中,使用vector作为该优先级队列的适配容器。 由于priority_queue也是一个适配器,所以它的接口函数

    2024年02月16日
    浏览(48)
  • 【C++】STL优先级队列(priority_queue)功能介绍以及模拟实现

    点进来的小伙伴不知道学过数据结构里的堆没有,如果学过的话,那就好说了,优先级队列就是堆,如果没学过,没关系,可以参考一下我之前写的一篇关于堆的博客,可以点进去看看:【数据结构】堆(包含堆排序和TOPK问题) 那么了解过堆了的话,我就不讲那么细致了,

    2024年02月16日
    浏览(49)
  • 【C++航海王:追寻罗杰的编程之路】priority_queue(优先队列) | 容器适配器你知道哪些?

    目录 1 - priority_queue的介绍和使用 1.1 - priority_queue的介绍 1.2 - priority_queue的使用 1.3 - priority_queue的模拟实现 2 - 容器适配器 2.1 - 什么是适配器 2.2 - STL标准库中stack和queue的底层结构 2.3 - deque的介绍 2.3.1 - deque的原理介绍 2.3.2 - deque的缺陷 2.4 - 为什么选择deque作为stack和queue的底

    2024年04月10日
    浏览(46)
  • 【STL】priority_queue(优先级队列)详解及仿函数使用(附完整源码)

    1. priority_queue介绍和使用 1.1 priority_queue介绍 优先级队列也是在 queue 里: 因此和 queue 一样, priority_queue 也是一个容器适配器。priority_queue官方文档 优先队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的。 类似于堆,在堆中可以随

    2024年02月08日
    浏览(42)
  • 优先级队列priority_queue

    关于less建大根堆,输出降序序列,greater建小根堆,输出升序序列,这点和sort()函数相反,参考我的这篇博客 底层原理 priority_queue底层维护着一个对应类型的,vector物理结构,但相当于堆排序的结构,这个vector逻辑结构是一个二叉堆; 每次 插入数据 ,我们插在堆尾(vector尾),

    2024年02月16日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包