【C++ STL】细数C++ STL 的那些事 -- priority_queue(优先队列)

2024-04-05 01:38

本文主要是介绍【C++ STL】细数C++ STL 的那些事 -- priority_queue(优先队列),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一,概述

           priority_queue是拥有权值观念的queue,它允许加入新元素,移除旧元素。调用 STL里面的 make_heap(), pop_heap(), push_heap() 算法实现,也算是堆的另外一种形式。但它是一个queue所以只允许在底端加入元素,在顶端移除元素。

           排序:按照权值大小顺序排序,而不是按照push 进去的顺序排序。权值高者排在前面,权值低者排在后面。

           允许以任何大小顺序插入到优先队列,但取出时是按照权值大小取。         

二,heap(堆)简介

        1)采用vector存储,是一颗完全二叉树(complete binary tree)的形式。

               heap分为 max_heap 和 min_heap,前者最大权值在根,后者最小权值在根。

        2)建立堆过程

              vector中元素先调整为堆的形式。

              插入元素时,将元素放到vector 的最后面end(),然后上溯调整堆。

        3)heap算法      // #include <algorithm>

               make_heap(first,last)       //初建堆

               push_heap(first,last)        //插入元素,并调整为堆

               pop_heap(first,last)         //弹出元素,并调整为堆

               sort_heap(first,last)         //堆排序

         4)示例

          

#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int main(int argc, char** argv) {int ia[9]={0,1,2,3,4,5,6,7,8};vector<int> ivec(ia,ia+9);make_heap(ivec.begin(),ivec.end()); //#include <algorithm>for(int i=0;i<ivec.size();++i)cout<<ivec[i]<<" ";cout<<endl;ivec.push_back(7);push_heap(ivec.begin(),ivec.end());for(int i=0;i<ivec.size();++i)cout<<ivec[i]<<" ";cout<<endl;pop_heap(ivec.begin(),ivec.end());  cout<<ivec.back()<<endl; //返回刚刚弹出的堆顶ivec.pop_back();         //将最后一个元素弹出数组for(int i=0;i<ivec.size();++i)cout<<ivec[i]<<" ";cout<<endl;sort_heap(ivec.begin(),ivec.end());for(int i=0;i<ivec.size();++i)cout<<ivec[i]<<" ";cout<<endl;return 0;
}

三,priority_queue 实例

#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;int main(int argc, char** argv) {int ia[9]={1,2,4,3,6,5,9,8,7};priority_queue<int>  ipq(ia,ia+9);cout<<"size:"<<ipq.size()<<endl;for(int i=0;i<ipq.size();++i)cout<<ipq.top()<<" ";cout<<endl;while(!ipq.empty()){cout<<ipq.top()<<" ";ipq.pop();}return 0;
}

       2)自己实现priority_queue 

             STL里面的 priority_queue 写法与此相似,只是增加了模板及相关的迭代器

#include <iostream>
#include <algorithm>
#include <vector>using namespace std;
class priority_queue
{private:vector<int> data;        public:void push( int t ){data.push_back(t);push_heap( data.begin(), data.end());//将动态数组vector中元素 建立成堆}        void pop(){pop_heap( data.begin(), data.end() ); //弹出堆顶元素,并调整堆data.pop_back();}        int top() { return data.front(); }int size() { return data.size(); }bool empty() { return data.empty(); }
};int main()
{priority_queue test;test.push( 3 );test.push( 5 );test.push( 2 );test.push( 4 );while( !test.empty() ){cout << test.top() << endl;test.pop(); }return 0;}

             3)STL里面默认用的是 vector. 比较方式默认用 operator< , 所以如果你把后面俩个参数缺省的话,优先队列就是大顶堆,队头元素最大。如果要用到小顶堆,则一般要把模板的三个参数都带进去。STL里面定义了一个仿函数 greater<>,对于基本类型可以用这个仿函数声明小顶堆

#include <iostream>
#include <queue>
#include <cstdlib>using namespace std;int main(){priority_queue<int, vector<int>, greater<int> > q;for( int i= 0; i< 10; ++i ) q.push( rand() );while( !q.empty() ){cout << q.top() << endl;q.pop();}return 0;
}

               4)对于自定义类型,则必须自己重载 operator< 或者自己写仿函数

#include <iostream>
#include <queue>
#include <cstdlib>using namespace std;struct Node{int x, y;Node( int a= 0, int b= 0 ):x(a), y(b) {} //初始化
};bool operator<( Node a, Node b ){if( a.x== b.x ) return a.y> b.y;elsereturn a.x> b.x;
}int main(){priority_queue<Node> q;for( int i= 0; i< 10; ++i )q.push( Node( rand(), rand() ) );while( !q.empty() ){cout << q.top().x << ' ' << q.top().y << endl;q.pop();}return 0;
}

                5)自定义类型重载 operator< 后,声明对象时就可以只带一个模板参数。但此时不能像基本类型这样声明priority_queue<Node, vector<Node>, greater<Node> >; 原因是 greater<Node> 没有定义,如果想用这种方法定义则可以按如下方式:

#include <iostream>
#include <queue>using namespace std;struct Node{int x, y;Node( int a= 0, int b= 0 ):x(a), y(b) {}
};struct cmp{bool operator() ( Node a, Node b ){if( a.x== b.x ) return a.y> b.y;return a.x> b.x; }
};int main(){priority_queue<Node, vector<Node>, cmp> q;for( int i= 0; i< 10; ++i )q.push( Node( rand(), rand() ) );while( !q.empty() ){cout << q.top().x << ' ' << q.top().y << endl;q.pop();}getchar();return 0;
} 





       


这篇关于【C++ STL】细数C++ STL 的那些事 -- priority_queue(优先队列)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/877348

相关文章

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s

poj 2431 poj 3253 优先队列的运用

poj 2431: 题意: 一条路起点为0, 终点为l。 卡车初始时在0点,并且有p升油,假设油箱无限大。 给n个加油站,每个加油站距离终点 l 距离为 x[i],可以加的油量为fuel[i]。 问最少加几次油可以到达终点,若不能到达,输出-1。 解析: 《挑战程序设计竞赛》: “在卡车开往终点的途中,只有在加油站才可以加油。但是,如果认为“在到达加油站i时,就获得了一

【C++高阶】C++类型转换全攻略:深入理解并高效应用

📝个人主页🌹:Eternity._ ⏩收录专栏⏪:C++ “ 登神长阶 ” 🤡往期回顾🤡:C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝