C++ STL 优先队列 (priority_queue)

nodejs中使用worker_threads来创建新的线程

std::priority_queue

<queue>

优先队列

  1、第一个元素始终为最大元素。

  2、有着类似于堆的特性,它可以在其中随时插入元素。

  3、支持下标访问(随机访问迭代器)

优先队列内部的实现需要依赖基础容器,该容器应可通过随机访问迭代器访问,并需要支持以下操作

  • empty( )

  • size( )

  • front( )

    Sentry(v20.12.1) K8S 云原生架构探索,JavaScript 性能监控之管理 Transactions

  • push_back( )

  • pop_back( )

     显而易见的是有dequevector这两个基础容器支持以上操作

     所以在默认情况下,如果未为priority_queue指定基础容器类,则将使用vector

成员函数

(constructor) Construct priority queue (public member function )
empty 优先队列是否为空
size 返回优先队列的当前元素个数
top 访问顶部元素(返回顶部元素的常量引用)
push 插入一个元素
pop 删除顶部元素
emplace 构造并插入一个元素
void swap (priority_queue& x) 交换两个队列的内容

注:
1、emplace 与 push 相比更加优化了对内存空间的使用,具体可以另行查询
2、swap 是交换两个同一类型的优先队列内的所有元素,如 a.swap ( x ) 即交换队列 a 和 x 的所有元素

构造优先队列

        <queue>
/* 1 */ priority_queue<int> pq1;                         //默认大根堆且默认基础容器为vector
/* 2 */ priority_queue<vector<int>, less<int> > pq2;     //与 1 的性质一模一样
/* 3 */ priority_queue<deque<int>, greater<int> > pq3;   //小根堆且基础容器为deque

注意:大根堆为less,小根堆为greater

函数成员用例

1、push、top、empty、pop、大根堆

(1)int
#include <iostream>
#include <queue>

using namespace std;

int main ( void )
{
    priority_queue<int> pq; //大根堆,默认降序(大的在前,小的在后)

    pq.push ( 60 );
    pq.push ( 20 );
    pq.push ( 40 );
    pq.push ( 1 );
    pq.push ( 25 );
    
    while ( !pq.empty() ) // pq不为空则循环
    {
        cout << pq.top() << " "; //添加新元素
        pq.pop();    //弹出头元素
    }

    return 0;
}

(2)string
#include <iostream>
#include <queue>

using namespace std;

int main ( void )
{
    priority_queue<string> pq; //大根堆,默认降序(大的在前,小的在后)

    pq.push ( "abc" );
    pq.push ( "abd" );
    pq.push ( "acd" );
    pq.push ( "cda" );
    pq.push ( "abcd" );
    
    while ( !pq.empty() ) // pq不为空则循环
    {
        cout << pq.top() << endl; //添加新元素
        pq.pop();    //弹出头元素
    }

    return 0;
}

输出按字典序

2、swap、emplace、小根堆

(1)输入输出
#include <iostream>
#include <queue>

using namespace std;

int main ( void )
{
    priority_queue<int, vector<int>, greater<int> > pq1; //小根堆,默认降序(小的在前,大的在后)

    pq1.emplace ( 5 );
    pq1.emplace ( 4 );
    pq1.emplace ( 3 );
    pq1.emplace ( 2 );
    pq1.emplace ( 1 );    

    priority_queue<int, vector<int>, greater<int> > pq2;

    pq2.emplace ( 5 * 2 );
    pq2.emplace ( 4 * 2 );
    pq2.emplace ( 3 * 2 );
    pq2.emplace ( 2 * 2 );
    pq2.emplace ( 1 * 2 );

    cout << "pq1:" << endl;
    while ( !pq1.empty() ) // pq不为空则循环
    {
        cout << pq1.top() << " "; //添加新元素
        pq1.pop();    //弹出头元素
    }
    
    cout << endl << "pq2:" << endl;
    while ( !pq2.empty() ) // pq不为空则循环
    {
        cout << pq2.top() << " "; //添加新元素
        pq2.pop();    //弹出头元素
    }
    cout << endl;
    
    return 0;
}

(2)利用swap高效地清空队列
void clear( priority_queue<int> &pq ) {
    priority_queue<int> empty;
    pq.swap ( empty );
}

STM32F207时钟系统解析

给TA买糖
共{{data.count}}人
人已赞赏
经验教程

C# 关机/重启/注销计算机以及关机关不掉原因整理

2021-1-21 19:37:00

经验教程

nodejs中使用worker_threads来创建新的线程

2021-1-21 20:25:00

⚠️
免责声明:根据《计算机软件保护条例》第十七条规定“为了学习和研究软件内含的设计思想和原理,通过安装、显示、传输或者存储软件等方式使用软件的,可以不经软件著作权人许可,不向其支付报酬。”您需知晓本站所有内容资源均来源于网络,仅供用户交流学习与研究使用,版权归属原版权方所有,版权争议与本站无关,用户本人下载后不能用作商业或非法用途,需在24个小时之内从您的电脑中彻底删除上述内容,否则后果均由用户承担责任;如果您访问和下载此文件,表示您同意只将此文件用于参考、学习而非其他用途,否则一切后果请您自行承担,如果您喜欢该程序,请支持正版软件,购买注册,得到更好的正版服务。 本站为个人博客非盈利性站点,所有软件信息均来自网络,所有资源仅供学习参考研究目的,并不贩卖软件,不存在任何商业目的及用途,网站会员捐赠是您喜欢本站而产生的赞助支持行为,仅为维持服务器的开支与维护,全凭自愿无任何强求。本站部份代码及教程来源于互联网,仅供网友学习交流,若您喜欢本文可附上原文链接随意转载。
无意侵害您的权益,请发送邮件至 momeis6@qq.com 或点击右侧 私信:momeis 反馈,我们将尽快处理。
0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
今日签到
有新私信 私信列表
搜索