c++ priority_queue用法 入门必看 超详细

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

1、priority_queue的作用

priority_queue即优先级队列,它的使用场景很多,它底层是用大小根堆实现的,可以用log(n)的时间动态地维护数据的有序性。适用于许多场景,比如简化哈夫曼树算法、dijkstra算法等等

priority_queue是不允许随机访问,只能访问队列首部的元素,也只能对首部元素进行出队,下面进行学习它的基本用法

2、priority_queue的定义

头文件

#include<queue>

基本定义方法:

基本定义默认是使用大顶堆的,即队首总是最大的元素

priority_queue<储存的类型> 容器名
如:

priority_queue<int> q;//储存int型数据 
priority_queue<double> q;//储存double型数据 
priority_queue<string> q;//储存string型数据 
priority_queue<结构体名> q;//储存结构体或者类 

快速切换大小顶堆定义:

less<储存的数据类型> 即使用大顶堆
greater<储存的数据类型> 即是用小顶堆

priority_queue<储存的类型,vector<储存的类型>,顶堆的类型> 容器名
如:

使用大顶堆的队列:

priority_queue<int,vector<int>,less<int>> q;//储存int型数据 
priority_queue<double,vector<double>,less<double>> q;//储存double型数据 
priority_queue<string,vector<string>,less<string>> q;//储存string型数据 
priority_queue<结构体名,vector<结构体名>,less<结构体名>> q;//储存结构体或者类 

使用小顶堆的队列:

priority_queue<int,vector<int>,greater<int>> q;//储存int型数据
priority_queue<double,vector<double>,greater<double>> q;//储存double型数据
priority_queue<string,vector<string>,greater<string>> q;//储存string型数据
priority_queue<结构体名,vector<结构体名>,greater<结构体名>> q;//储存结构体或者类 

使用结构体重载运算符定义:

新建一个结构体,通过重载运算符改变顶堆的排序,这里是拓展用法,也是必学用法,因为自己写的结构体是没有比较大小功能的,当然也可以在原本的结构体里面重载运算符

priority_queue<int,vector<int>,cmp> q;//储存int型数据 
priority_queue<double,vector<double>,cmp> q;//储存double型数据 
priority_queue<string,vector<string>,cmp> q;//储存string型数据
priority_queue<结构体名,vector<结构体名>,cmp> q;//储存结构体或者类 

3、priority_queue的成员函数

empty() 如果优先队列为空,则返回真 
pop() 删除第一个元素 
push() 加入一个元素 
size() 返回优先队列中拥有的元素的个数 
top() 返回优先队列中有最高优先级的元素 

4、priority_queue的基本用法

普通数据类型的使用方法:

示例代码:

#include<iostream>//c++标准头文件,可以使用cout,cin等标准库函数 
#include<queue>//使用priority_queue时需要的头文件 
using namespace std;//命名空间,防止重名给程序带来各种隐患,使用cin,cout,stack,map,set,vector,queue时都要使用
int main(){
	 priority_queue<int> q1;//定义一个默认大顶堆的优先级队列q1,即队首元素总是最大值 
//	 priority_queue<int,vector<int>,less<int>> q1; //这样显示定义大顶堆也是可以的 
	 cout<<"定义默认大顶堆q1: priority_queue<int> q1"<<endl;
	 q1.push(10);//添加一个元素10 
	 q1.push(5);//添加一个元素5
	 q1.push(7);//添加一个元素7 
	 cout<<"按顺序插入10、5、7这三个数据,目前优先级队列中的元素:10 5 7"<<endl; 
	 cout<<"q1.size()="<<q1.size()<<endl;//查看目前队列中元素个数 
	 cout<<"q1.empty()="<<q1.empty()<<endl;//查看目前队列是否为空,1即为空,0即非空 
	 cout<<"q1.top()="<<q1.top()<<endl;//查看目前队列首部元素
	 cout<<endl;
	 
	 q1.pop(); 
	 cout<<"q1.pop()后,目前优先级队列中的元素:5 7"<<endl; 
	 cout<<"q1.size()="<<q1.size()<<endl;
	 cout<<"q1.empty()="<<q1.empty()<<endl;
	 cout<<"q1.top()="<<q1.top()<<endl;
	 cout<<endl;
	 
	 q1.pop(); 
	 cout<<"q1.pop()后,目前优先级队列中的元素:5"<<endl; 
	 cout<<"q1.size()="<<q1.size()<<endl;
	 cout<<"q1.empty()="<<q1.empty()<<endl;
	 cout<<"q1.top()="<<q1.top()<<endl;
	 cout<<endl;
	 
	 q1.pop(); 
	 cout<<"q1.pop()后,目前优先级队列是空的"<<endl; 
	 cout<<"q1.size()="<<q1.size()<<endl;
	 cout<<"q1.empty()="<<q1.empty()<<endl;
	 cout<<"队列为空时不允许使用q1.top()查看队首元素"<<endl;
	 
	 cout<<endl<<endl;
	 
	 
	 
	 
	 priority_queue<int,vector<int>,greater<int>> q2; //定义一个小顶堆的优先级队列q2,即队首元素总是最小值 
	 
	 cout<<"定义小顶堆q2: priority_queue<int,vector<int>,greater<int>> q2"<<endl;
	 q2.push(10);//添加一个元素10 
	 q2.push(5);//添加一个元素5
	 q2.push(7);//添加一个元素7 
	 cout<<"按顺序插入10、5、7这三个数据,目前优先级队列中的元素:10 5 7"<<endl; 
	 cout<<"q2.size()="<<q2.size()<<endl;//查看目前队列中元素个数 
	 cout<<"q2.empty()="<<q2.empty()<<endl;//查看目前队列是否为空,1即为空,0即非空 
	 cout<<"q2.top()="<<q2.top()<<endl;//查看目前队列首部元素
	 cout<<endl;
	 
	 q2.pop(); 
	 cout<<"q2.pop()后,目前优先级队列中的元素:10 7"<<endl; 
	 cout<<"q2.size()="<<q2.size()<<endl;
	 cout<<"q2.empty()="<<q2.empty()<<endl;
	 cout<<"q2.top()="<<q2.top()<<endl;
	 cout<<endl;
	 
	 q2.pop(); 
	 cout<<"q2.pop()后,目前优先级队列中的元素:10"<<endl; 
	 cout<<"q2.size()="<<q2.size()<<endl;
	 cout<<"q2.empty()="<<q2.empty()<<endl;
	 cout<<"q2.top()="<<q2.top()<<endl;
	 cout<<endl;
	 
	 q2.pop(); 
	 cout<<"q2.pop()后,目前优先级队列是空的"<<endl; 
	 cout<<"q2.size()="<<q2.size()<<endl;
	 cout<<"q2.empty()="<<q2.empty()<<endl;
	 cout<<"队列为空时不允许使用q1.top()查看队首元素"<<endl;
	 
}

运行结果:

定义默认大顶堆q1: priority_queue<int> q1
按顺序插入1057这三个数据,目前优先级队列中的元素:10 5 7
q1.size()=3
q1.empty()=0
q1.top()=10

q1.pop()后,目前优先级队列中的元素:5 7
q1.size()=2
q1.empty()=0
q1.top()=7

q1.pop()后,目前优先级队列中的元素:5
q1.size()=1
q1.empty()=0
q1.top()=5

q1.pop()后,目前优先级队列是空的
q1.size()=0
q1.empty()=1
队列为空时不允许使用q1.top()查看队首元素


定义小顶堆q2: priority_queue<int,vector<int>,greater<int>> q2
按顺序插入1057这三个数据,目前优先级队列中的元素:10 5 7
q2.size()=3
q2.empty()=0
q2.top()=5

q2.pop()后,目前优先级队列中的元素:10 7
q2.size()=2
q2.empty()=0
q2.top()=7

q2.pop()后,目前优先级队列中的元素:10
q2.size()=1
q2.empty()=0
q2.top()=10

q2.pop()后,目前优先级队列是空的
q2.size()=0
q2.empty()=1
队列为空时不允许使用q1.top()查看队首元素

结构体类型的使用方法

方法一、函数里重载运算符

由于结构体默认是没有比较大小的功能的,所以也就不能直接使用优先级队列,需要重载运行符大于号和小于号,然后使用less<>和greater<>切换大小顶堆

示例代码:

#include<iostream>//c++标准头文件,可以使用cout,cin等标准库函数 
#include<queue>//使用priority_queue时需要的头文件 
using namespace std;//命名空间,防止重名给程序带来各种隐患,使用cin,cout,stack,map,set,vector,queue时都要使用
struct test{//定义一个结构体test 
	int val;
	test(int v){//构造函数 
		this->val=v;
	}
	bool operator > (const test t)const{//重载运算符> 
		return val>t.val;
	}
	bool operator < (const test t)const{//重载运算符
		return val<t.val;
	}
};
int main(){
	priority_queue<test,vector<test>,less<test>> q1;//定义一个大顶堆q1 
	cout<<"定义一个大根堆q1: priority_queue<test,vector<test>,less<test>> q1"<<endl; 
	q1.push(test(10));//向队列中添加一个test,val的值为10 
	q1.push(test(5));//向队列中添加一个test,val的值为5
	q1.push(test(7));//向队列中添加一个test,val的值为7
	cout<<"按顺序添加val的值为10、5、7的test,目前队列的元素:test(10) test(5) test(7)" <<endl; 
	cout<<"q1.top().val="<<q1.top().val<<endl;
	cout<<endl; 
	
	
	q1.pop();
	cout<<"q1.pop()后,目前队列的元素:test(5) test(7)"<<endl; 
	cout<<"q1.top().val="<<q1.top().val<<endl;
	cout<<endl; 
	
	
	q1.pop();
	cout<<"q1.pop()后,目前队列的元素:test(5)"<<endl; 
	cout<<"q1.top().val="<<q1.top().val<<endl;
	cout<<endl; 
	
	q1.pop();
	cout<<"q1.pop()后,目前队列是空的"<<endl; 
	cout<<"目前队列是空的,不能使用q1.top()查询队首元素"<<endl;
	cout<<endl<<endl; 
	
	
	
	priority_queue<test,vector<test>,greater<test>> q2;//定义一个大顶堆q1 
	cout<<"定义一个小根堆q2: priority_queue<test,vector<test>,greate<test>> q2"<<endl; 
	q2.push(test(10));//向队列中添加一个test,val的值为10 
	q2.push(test(5));//向队列中添加一个test,val的值为5
	q2.push(test(7));//向队列中添加一个test,val的值为7
	cout<<"按顺序添加val的值为10、5、7的test,目前队列的元素:test(10) test(5) test(7)" <<endl; 
	cout<<"q2.top().val="<<q2.top().val<<endl;
	cout<<endl; 
	
	
	q2.pop();
	cout<<"q2.pop()后,目前队列的元素:test(10) test(7)"<<endl; 
	cout<<"q2.top().val="<<q2.top().val<<endl;
	cout<<endl; 
	
	
	q2.pop();
	cout<<"q2.pop()后,目前队列的元素:test(10)"<<endl; 
	cout<<"q2.top().val="<<q2.top().val<<endl;
	cout<<endl; 
	
	q2.pop();
	cout<<"q1.pop()后,目前队列是空的"<<endl; 
	cout<<"目前队列是空的,不能使用q2.top()查询队首元素"<<endl;
	
	
}

运行结果:

#include<iostream>//c++标准头文件,可以使用cout,cin等标准库函数 
#include<queue>//使用priority_queue时需要的头文件 
using namespace std;//命名空间,防止重名给程序带来各种隐患,使用cin,cout,stack,map,set,vector,queue时都要使用
struct test{//定义一个结构体test 
	int val;
	test(int v){//构造函数 
		this->val=v;
	}
	bool operator > (const test t)const{//重载运算符> 
		return val>t.val;
	}
	bool operator < (const test t)const{//重载运算符
		return val<t.val;
	}
};
int main(){
	priority_queue<test,vector<test>,less<test>> q1;//定义一个大顶堆q1 
	cout<<"定义一个大根堆q1: priority_queue<test,vector<test>,less<test>> q1"<<endl; 
	q1.push(test(10));//向队列中添加一个test,val的值为10 
	q1.push(test(5));//向队列中添加一个test,val的值为5
	q1.push(test(7));//向队列中添加一个test,val的值为7
	cout<<"按顺序添加val的值为10、5、7的test,目前队列的元素:test(10) test(5) test(7)" <<endl; 
	cout<<"q1.top().val="<<q1.top().val<<endl;
	cout<<endl; 
	
	
	q1.pop();
	cout<<"q1.pop()后,目前队列的元素:test(5) test(7)"<<endl; 
	cout<<"q1.top().val="<<q1.top().val<<endl;
	cout<<endl; 
	
	
	q1.pop();
	cout<<"q1.pop()后,目前队列的元素:test(5)"<<endl; 
	cout<<"q1.top().val="<<q1.top().val<<endl;
	cout<<endl; 
	
	q1.pop();
	cout<<"q1.pop()后,目前队列是空的"<<endl; 
	cout<<"目前队列是空的,不能使用q1.top()查询队首元素"<<endl;
	cout<<endl<<endl; 
	
	
	
	priority_queue<test,vector<test>,greater<test>> q2;//定义一个大顶堆q1 
	cout<<"定义一个小根堆q2: priority_queue<test,vector<test>,greate<test>> q2"<<endl; 
	q2.push(test(10));//向队列中添加一个test,val的值为10 
	q2.push(test(5));//向队列中添加一个test,val的值为5
	q2.push(test(7));//向队列中添加一个test,val的值为7
	cout<<"按顺序添加val的值为10、5、7的test,目前队列的元素:test(10) test(5) test(7)" <<endl; 
	cout<<"q2.top().val="<<q2.top().val<<endl;
	cout<<endl; 
	
	
	q2.pop();
	cout<<"q2.pop()后,目前队列的元素:test(10) test(7)"<<endl; 
	cout<<"q2.top().val="<<q2.top().val<<endl;
	cout<<endl; 
	
	
	q2.pop();
	cout<<"q2.pop()后,目前队列的元素:test(10)"<<endl; 
	cout<<"q2.top().val="<<q2.top().val<<endl;
	cout<<endl; 
	
	q2.pop();
	cout<<"q1.pop()后,目前队列是空的"<<endl; 
	cout<<"目前队列是空的,不能使用q2.top()查询队首元素"<<endl;
	
	
}

方法二、自定义结构体重载括号运算符

很多时候,我们不应该重载结构体的运算符。像数据结构vector,它有它的基本运算方法,我们不应该重载它的运算符。
此时,我们就应该自定义结构体替代less<>和greater<>,通过重载括号符就可以更改比较规则

示例代码:

#include<iostream>//c++标准头文件,可以使用cout,cin等标准库函数 
#include<queue>//使用priority_queue时需要的头文件 
using namespace std;//命名空间,防止重名给程序带来各种隐患,使用cin,cout,stack,map,set,vector,queue时都要使用
struct test{//定义一个结构体test 
	int val;
	test(int v){//构造函数 
		this->val=v;
	}
//	下面是基本的运算方法,我们不能随意更改它 
	bool operator > (const test t)const{//重载运算符
		return val>t.val;
	}
	bool operator < (const test t)const{//重载运算符
		return val<t.val;
	}
};

struct cmp{
	bool operator () (const test t1,const test t2)const{//重载括号运算符
		return t1.val<t2.val;//小于号是大根堆,大于号是小根堆 
	}
};
int main(){
	priority_queue<test,vector<test>,cmp> q;//自定义一个优先级队列q 
	cout<<"自定义一个优先级队列q: priority_queue<test,vector<test>,cmp> q"<<endl; 
	q.push(test(10));//向队列中添加一个test,val的值为10 
	q.push(test(5));//向队列中添加一个test,val的值为5
	q.push(test(7));//向队列中添加一个test,val的值为7
	cout<<"q.top().val="<<q.top().val<<endl;
	cout<<endl; 
	
	
	q.pop();
	cout<<"q.top().val="<<q.top().val<<endl;
	cout<<endl; 
	
	q.pop();
	cout<<"q.top().val="<<q.top().val<<endl;
	cout<<endl; 
	
	q.pop();
	cout<<"目前队列是空的,不能使用q.top()查询队首元素"<<endl;
	
	
}

运行结果:

自定义一个优先级队列q: priority_queue<test,vector<test>,cmp> q
q.top().val=10

q.top().val=7

q.top().val=5

目前队列是空的,不能使用q.top()查询队首元素

把括号运算符里的小于号改为大于号就是小顶堆了

自定义一个优先级队列q: priority_queue<test,vector<test>,cmp> q
q.top().val=5

q.top().val=7

q.top().val=10

目前队列是空的,不能使用q.top()查询队首元素

至此,优先级队列的基本用法就学完啦

是不是很简单呢?

刚接触肯定会觉得难,多些做题多些用,熟悉了就容易了,兄弟萌,加油!!!

文章尚有不足,欢迎大牛们指正

感谢观看,点个赞吧文章来源地址https://www.toymoban.com/news/detail-664084.html

到了这里,关于c++ priority_queue用法 入门必看 超详细的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • C++ STL priority_queue

    目录 一.认识priority_queue 二. priority_queue的使用 三.仿函数  1.什么是仿函数  2.控制大小堆  3.TopK问题 四.模拟实现priority_queue  1.priority_queue的主要接口框架  2.堆的向上调整算法  3.堆的向下调整算法  4.仿函数控制大小堆  五.priority_queue模拟实现整体代码和测试 priority_queue-

    2024年02月07日
    浏览(43)
  • C++ | 仿函数与priority_queue

    目录 前言 一、初始仿函数 1、仿函数是什么 2、仿函数的使用  二、优先级队列 1、 优先级队列的基本概念 2、堆的储存结构与结点之前关系 3、堆的使用 4、堆的模拟实现         本文主要介绍优先级队列与仿函数,优先级队列实际上是我们在数据结构中学的堆;在介绍

    2024年02月15日
    浏览(38)
  • C++优先队列(priority_queue)详解

    目录 一、 定义 二、优先队列内元素访问 三、优先队列常用函数 四、优先队列内元素的优先级          优先队列(priority_queue),底层的数据结构为 堆(heap) ,以此 保证队首元素一定是当前队列所有元素中优先级最高的。 我们也可以随时往优先队里面加入(push)元素,其队

    2024年02月16日
    浏览(43)
  • C++ 优先队列 priority_queue 使用篇

    目录 1.储备知识    (1)数据结构:堆   (2)仿函数(函数对象)     [1]理解仿函数     [2]实现仿函数   (3)priority_queue理解     [1]什么是priority_queue (优先队列)?     [2]优先队列性质 2.priority_queue的参数理解(重要!!!)   (1)priority_queue的参数     [1]priority_queue类模板参数     [

    2024年03月12日
    浏览(83)
  • 【C++】priority_queue使用与模拟实现

    🚀 作者简介:一名在后端领域学习,并渴望能够学有所成的追梦人。 🚁 个人主页:不 良 🔥 系列专栏:🛸C++  🛹Linux 📕 学习格言:博观而约取,厚积而薄发 🌹 欢迎进来的小伙伴,如果小伙伴们在学习的过程中,发现有需要纠正的地方,烦请指正,希望能够与诸君一同

    2024年02月16日
    浏览(44)
  • C++中的优先队列(priority_queue)

    什么是优先队列 优先队列(priority queue) 普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有优先级最高先出的性质。通常采用堆数据结构来实现。

    2024年02月15日
    浏览(48)
  • C++:模版进阶 | Priority_queue的模拟实现

                                                创作不易,感谢三连支持  模板参数分类为 类型形参与非类型形参 。 类型形参即:出现在模板参数列表中,跟在class或者typename之类的参数类型名称。 非类型形参,就是 用一个常量作为类(函数)模板的一个参数 ,在类(函数

    2024年03月12日
    浏览(44)
  • [C++]priority_queue的介绍及模拟实现

    目录 priority_queue的介绍及模拟实现::                                                         priority_queue的介绍                                                         priority_queue的定义方式                 

    2024年02月04日
    浏览(45)
  • 【C++】STL之priority_queue类源码剖析

    目录 概述 算法 源码 PriorityQueue.h test.cpp 测试结果 priority_queue:优先级队列,包含在头文件queue中 优先级队列类似于堆结构,优先级最高的元素被置为堆顶,最优先被弹出top()和删除pop() 优先级队列的默认调整策略是大根堆,也就是最大值在堆顶 自定义类型需要用户自己提供

    2024年02月02日
    浏览(41)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包