详解c++优先队列priority_queue的用法

既然是队列那么先要包含头文件#include <queue>, 他和queue不同的就在于我们可以自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队

优先队列具有队列的所有特性，包括基本操作，只是在这基础上添加了内部的一个排序，它本质是一个堆实现的

和队列基本操作相同:

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

定义：priority_queue<Type, Container, Functional>

Type 就是数据类型，Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆

一般是：

//升序队列
priority_queue <int,vector<int>,greater<int> > q;
//降序队列
priority_queue <int,vector<int>,less<int> >q;

//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）

1.基本类型例子：

#include<iostream>
#include <queue>
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;
}

输出

4 3 2 1 0
0 1 2 3 4
cbd abcd abc

2.pari的比较，先比较第一个元素，第一个相等比较第二个

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main()
{
    priority_queue<pair<int, int> > a;
    pair<int, int> b(1, 2);
    pair<int, int> c(1, 3);
    pair<int, int> d(2, 5);
    a.push(d);
    a.push(c);
    a.push(b);
    while (!a.empty())
    {
        cout << a.top().first << ' ' << a.top().second << '\n';
        a.pop();
    }
}

输出

2 5
1 3
1 2

3.对于自定义类型

#include <iostream>
#include <queue>
using namespace std;

//方法1
struct tmp1 //运算符重载<
{
    int x;
    tmp1(int a) {x = a;}
    bool operator<(const tmp1& a) const
    {
        return x < a.x; //大顶堆
    }
};

//方法2
struct tmp2 //重写仿函数
{
    bool operator() (tmp1 a, tmp1 b)
    {
        return a.x < b.x; //大顶堆
    }
};

int main()
{
    tmp1 a(1);
    tmp1 b(2);
    tmp1 c(3);
    priority_queue<tmp1> d;
    d.push(b);
    d.push(c);
    d.push(a);
    while (!d.empty())
    {
        cout << d.top().x << '\n';
        d.pop();
    }
    cout << endl;

    priority_queue<tmp1, vector<tmp1>, tmp2> f;
    f.push(c);
    f.push(b);
    f.push(a);
    while (!f.empty())
    {
        cout << f.top().x << '\n';
        f.pop();
    }
}

输出

3
2
1

3
2
1

以上所述是小编给大家介绍的详解c++优先队列priority_queue的用法，希望对大家有所帮助。在此也非常感谢大家对我们网站的支持！

赞 (0)

相关推荐

  • C++ STL priority_queue自定义排序实现方法详解

    前面讲解 priority_queue 容器适配器时,还遗留一个问题,即当 <function> 头文件提供的排序方式(std::less<T> 和 std::greater<T>)不再适用时,如何自定义一个满足需求的排序规则. 首先,无论 priority_queue 中存储的是基础数据类型(int.double 等),还是 string 类对象或者自定义的类对象,都可以使用函数对象的方式自定义排序规则.例如: #include<iostream> #in

  • C++ 中"priority_queue" 优先级队列实例详解

    C++ 中"priority_queue" 优先级队列实例详解 1. 简介 标准库队列使用了先进先出(FIFO)的存储和检索策略. 进入队列的对象被放置在尾部, 下一个被取出的元素则取自队列的首部. 标准库提供了两种风格的队列: FIFO 队列(FIFO queue, 简称 queue), 以及优先级队列(priority queue). priority_queue 允许用户为队列中存储的元素设置优先级. 这种队列不是直接将新元素放置在队列尾部, 而是放在比它优先级低的元素前面. 标

  • C++中priority_queue模拟实现的代码示例

    目录 priority_queue概述 priority_queue定义 priority_queue特点 构造函数 修改相关函数 push pop 容量相关函数 size empty 元素访问相关函数 top 总结 priority_queue概述 priority_queue定义 优先级队列是不同于先进先出队列的另一种队列.每次从队列中取出的是具有最高优先权的元素. priority_queue特点 优先队列是一种容器适配器,首先要包含头文件 #include<queue>, 他和queu

  • 优先队列(priority_queue)的C语言实现代码

    优先队列(priority_queue)和一般队列(queue)的函数接口一致,不同的是,优先队列每次出列的是整个队列中最小(或者最大)的元素. 本文简要介绍一种基于数组二叉堆实现的优先队列,定义的数据结构和实现的函数接口说明如下: 一.键值对结构体:KeyValue 复制代码 代码如下: // =============KeyValue Struct==================================typedef struct key_value_struct KeyValu

  • C++ 容器适配器priority_queue的使用及实现代码

    C++ 容器适配器priority_queue的使用及实现代码

    优先级队列(Priority Queue) 队列是一种特征为FIFO的数据结构,每次从队列中取出的是最早加入队列中的元素.但是,许多应用需要另一种队列,每次从队列中取出的应是具有最高优先权的元素,这种队列就是优先级队列(Priority Queue),也称为优先权队列. 1. 优先级队列的概念 优先级队列的定义 优先级队列是不同于先进先出队列的另一种队列.每次从队列中取出的是具有最高优先权的元素. 优先级队列的特点 优先级队列是0个或多个元素的集合,每个元素都有一个优先权或值. 当给每个元素分配

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

    普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除. 在优先队列中,元素被赋予优先级.当访问元素时,具有最高优先级的元素最先删除.优先队列具有最高级先出 (first in, largest out)的行为特征. 首先要包含头文件#include<queue>, 他和queue不同的就在于我们可以自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队. 优先队列具有队列的所有特性,包括队列的基本操作,只是在这基础上添加了内部的一个排序,它本质是一个堆实现的. 和队列基本

  • 详解c++优先队列priority_queue的用法

    既然是队列那么先要包含头文件#include <queue>, 他和queue不同的就在于我们可以自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队 优先队列具有队列的所有特性,包括基本操作,只是在这基础上添加了内部的一个排序,它本质是一个堆实现的 和队列基本操作相同: top 访问队头元素 empty 队列是否为空 size 返回队列内元素个数 push 插入元素到队尾 (并排序) emplace 原地构造一个元素并插入队列 pop 弹出队头元素 swap 交换内容 定义:prio

  • 详解Oracle游标的简易用法

    下面看下Oracle游标的简易用法,具体代码如下所示: create or replace procedure NW_DelYW(iOPERATION_ID number, sUserID varchar2) is sCurDJBH yw_operation_link.djbh%type; cursor table_yw(ywid yw_operation.id%type) is select * from yw_operation_link t1 where t1.operation_id =

  • Node.js API详解之 tty功能与用法实例分析

    本文实例讲述了Node.js API详解之 tty功能与用法.分享给大家供大家参考,具体如下: tty 可以理解为终端的意思.tty 模块提供终端相关的接口,用来获取终端的行数列数等. 通过 const tty = require('tty'); 的方式引用 tty 模块 process.stdout.isTTY 说明: 此属性位于 process 模块,用来判断 Node.js 是否运行在一个 TTY 环境中 demo: console.log(process.stdout.isTTY) //

  • 详解shell 变量的高级用法示例

    变量删除和替换 案例:从头开始匹配,将符合最短的数据删除 (#) variable_1="I love you, Do you love me" echo $variable_1 variable_2=${variable_1#*ov} echo $variable_2 案例:从头开始匹配,将复合最短的数据删除(##) varible_3=${variable_1##*ov} echo $varible_3 案例:替换字符串,只替换第一次匹配成功的(/) echo $PATH var6

  • 详解C# 中Session的用法

    Session模型简介 在学习之前我们会疑惑,Session是什么呢?简单来说就是服务器给客户端的一个编号.当一台WWW服务器运行时,可能有若干个用户浏览正在运正在这台服务器上的网站.当每 个用户首次与这台WWW服务器建立连接时,他就与这个服务器建立了一个Session,同时服务器会自动为其分配一个SessionID,用以标识这个用 户的唯一身份.这个SessionID是由WWW服务器随机产生的一个由24个字符组成的字符串,我们会在下面的实验中见到它的实际样子. 这个唯一的SessionID是有

  • 详解C++中mutable的用法

    代码编译运行环境:VS2017+Win32+Debug mutalbe的中文意思是"可变的,易变的",是constant(即C++中的const)的反义词.在C++中,mutable也是为了突破const的限制而设置的,被mutable修饰的变量将永远处于可变的状态. mutable的作用有两点: (1)保持常量对象中大部分数据成员仍然是"只读"的情况下,实现对个别数据成员的修改: (2)使类的const函数可以修改对象的mutable数据成员. 使用mutable

  • 详解Docker Swarm概念与用法

    Docker Swarm是Docker公司开发的容器集群管理服务.从1.12.0版本开始,已经是Docker安装后自带的一部分(捆绑软件)了,又称为Swarm Mode,无需额外安装. 与Kubernetes相比,Docker Swarm是一个简单的软件,似乎不堪大用.但是它与docker-compose兼容的优点,可以弥补一切.对于没有集群使用经验的小白,用Docker Swarm起步,是一个很好的选择. 概念 Docker Swarm,主要包含以下概念: Swarm Node Stack S

  • 详解c# 接口IDisposable的用法

    C#的每一个类型都代表一种资源,而资源又分为两类: 托管资源  由CLR管理分配和释放的资源,即从CLR里new出来的对象. 非托管资源  不受CLR管理的对象,如Windows内核对象,或者文件.数据库连接.套接字.COM对象等. 如果类型用到了非托管资源,或者需要显式释放托管资源,那么需要让类型继承接口IDisposable.记住:如果类型需要显式释放资源,那么一定要继承IDisposable接口.如: class SampleClass:IDisposable { private IntP

  • 详解Golang中Channel的用法

    如果说goroutine是Go语言程序的并发体的话,那么channels则是它们之间的通信机制.一个channel是一个通信机制,它可以让一个goroutine通过它给另一个goroutine发送值信息. 1 创建channel 每个channel都有一个特殊的类型,也就是channels可发送数据的类型.一个可以发送int类型数据 的channel一般写为chan int.使用内置的make函数,如果第二个参数大于0,则表示创建一个带缓存的channel. ch := make(chan in

  • 详解Python的lambda函数用法

    lambda函数用法 lambda非常重要的一个定义.lambda在[运行时]才绑定,[不是]在定义的时候绑定.下面这个列子: 本意想:让X分别与0到1的数相加.x+0,x+1,x+2,x+3 实际运行结果是: 0 0 0 0 原因就是上面提到的,运行时才绑定.先运行的for循环,无法捕捉到循环. func = [lambda x: x + n for n in range(4)] # x+n,n是从0到3 For循环,x+0,x+1,x+3 for f in func: print(f(0))

随机推荐