算法 数据结构 c++ priority

1、priority_queue的作用

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

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

2、priority_queue的定义

头文件

#include

基本定义方法：

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

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

priority_queue q;//储存int型数据

priority_queue q;//储存double型数据

priority_queue q;//储存string型数据

priority_queue<结构体名> q;//储存结构体或者类

快速切换大小顶堆定义：

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

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

使用大顶堆的队列：

priority_queue,less> q;//储存int型数据

priority_queue,less> q;//储存double型数据

priority_queue,less> q;//储存string型数据

priority_queue<结构体名,vector<结构体名>,less<结构体名>> q;//储存结构体或者类

使用小顶堆的队列：

priority_queue,greater> q;//储存int型数据

priority_queue,greater> q;//储存double型数据

priority_queue,greater> q;//储存string型数据

priority_queue<结构体名,vector<结构体名>,greater<结构体名>> q;//储存结构体或者类

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

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

priority_queue,cmp> q;//储存int型数据

priority_queue,cmp> q;//储存double型数据

priority_queue,cmp> q;//储存string型数据

priority_queue<结构体名,vector<结构体名>,cmp> q;//储存结构体或者类

3、priority_queue的成员函数

empty() 如果优先队列为空，则返回真

pop() 删除第一个元素

push() 加入一个元素

size() 返回优先队列中拥有的元素的个数

top() 返回优先队列中有最高优先级的元素

4、priority_queue的基本用法

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

示例代码：

#include//c++标准头文件，可以使用cout,cin等标准库函数

#include//使用priority_queue时需要的头文件

using namespace std;//命名空间，防止重名给程序带来各种隐患，使用cin,cout,stack,map,set,vector,queue时都要使用

int main(){

priority_queue q1;//定义一个默认大顶堆的优先级队列q1，即队首元素总是最大值

// priority_queue,less> q1; //这样显示定义大顶堆也是可以的

cout<<"定义默认大顶堆q1: priority_queue q1"<

q1.push(10);//添加一个元素10

q1.push(5);//添加一个元素5

q1.push(7);//添加一个元素7

cout<<"按顺序插入10、5、7这三个数据，目前优先级队列中的元素：10 5 7"<

cout<<"q1.size()="<

cout<<"q1.empty()="<

cout<<"q1.top()="<

cout<

q1.pop();

cout<<"q1.pop()后，目前优先级队列中的元素：5 7"<

cout<<"q1.size()="<

cout<<"q1.empty()="<

cout<<"q1.top()="<

cout<

q1.pop();

cout<<"q1.pop()后，目前优先级队列中的元素：5"<

cout<<"q1.size()="<

cout<<"q1.empty()="<

cout<<"q1.top()="<

cout<

q1.pop();

cout<<"q1.pop()后，目前优先级队列是空的"<

cout<<"q1.size()="<

cout<<"q1.empty()="<

cout<<"队列为空时不允许使用q1.top()查看队首元素"<

cout<

priority_queue,greater> q2; //定义一个小顶堆的优先级队列q2，即队首元素总是最小值

cout<<"定义小顶堆q2: priority_queue,greater> q2"<

q2.push(10);//添加一个元素10

q2.push(5);//添加一个元素5

q2.push(7);//添加一个元素7

cout<<"按顺序插入10、5、7这三个数据，目前优先级队列中的元素：10 5 7"<

cout<<"q2.size()="<

cout<<"q2.empty()="<

cout<<"q2.top()="<

cout<

q2.pop();

cout<<"q2.pop()后，目前优先级队列中的元素：10 7"<

cout<<"q2.size()="<

cout<<"q2.empty()="<

cout<<"q2.top()="<

cout<

q2.pop();

cout<<"q2.pop()后，目前优先级队列中的元素：10"<

cout<<"q2.size()="<

cout<<"q2.empty()="<

cout<<"q2.top()="<

cout<

q2.pop();

cout<<"q2.pop()后，目前优先级队列是空的"<

cout<<"q2.size()="<

cout<<"q2.empty()="<

cout<<"队列为空时不允许使用q1.top()查看队首元素"<

}

运行结果：

定义默认大顶堆q1: priority_queue q1

按顺序插入10、5、7这三个数据，目前优先级队列中的元素：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,greater> q2

按顺序插入10、5、7这三个数据，目前优先级队列中的元素：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//c++标准头文件，可以使用cout,cin等标准库函数

#include//使用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

}

};

int main(){

priority_queue,less> q1;//定义一个大顶堆q1

cout<<"定义一个大根堆q1: priority_queue,less> q1"<

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)" <

cout<<"q1.top().val="<

cout<

q1.pop();

cout<<"q1.pop()后，目前队列的元素：test(5) test(7)"<

cout<<"q1.top().val="<

cout<

q1.pop();

cout<<"q1.pop()后，目前队列的元素：test(5)"<

cout<<"q1.top().val="<

cout<

q1.pop();

cout<<"q1.pop()后，目前队列是空的"<

cout<<"目前队列是空的，不能使用q1.top()查询队首元素"<

cout<

priority_queue,greater> q2;//定义一个大顶堆q1

cout<<"定义一个小根堆q2: priority_queue,greate> q2"<

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)" <

cout<<"q2.top().val="<

cout<

q2.pop();

cout<<"q2.pop()后，目前队列的元素：test(10) test(7)"<

cout<<"q2.top().val="<

cout<

q2.pop();

cout<<"q2.pop()后，目前队列的元素：test(10)"<

cout<<"q2.top().val="<

cout<

q2.pop();

cout<<"q1.pop()后，目前队列是空的"<

cout<<"目前队列是空的，不能使用q2.top()查询队首元素"<

}

运行结果：

#include//c++标准头文件，可以使用cout,cin等标准库函数

#include//使用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

}

};

int main(){

priority_queue,less> q1;//定义一个大顶堆q1

cout<<"定义一个大根堆q1: priority_queue,less> q1"<

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)" <

cout<<"q1.top().val="<

cout<

q1.pop();

cout<<"q1.pop()后，目前队列的元素：test(5) test(7)"<

cout<<"q1.top().val="<

cout<

q1.pop();

cout<<"q1.pop()后，目前队列的元素：test(5)"<

cout<<"q1.top().val="<

cout<

q1.pop();

cout<<"q1.pop()后，目前队列是空的"<

cout<<"目前队列是空的，不能使用q1.top()查询队首元素"<

cout<

priority_queue,greater> q2;//定义一个大顶堆q1

cout<<"定义一个小根堆q2: priority_queue,greate> q2"<

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)" <

cout<<"q2.top().val="<

cout<

q2.pop();

cout<<"q2.pop()后，目前队列的元素：test(10) test(7)"<

cout<<"q2.top().val="<

cout<

q2.pop();

cout<<"q2.pop()后，目前队列的元素：test(10)"<

cout<<"q2.top().val="<

cout<

q2.pop();

cout<<"q1.pop()后，目前队列是空的"<

cout<<"目前队列是空的，不能使用q2.top()查询队首元素"<

}

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

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

示例代码：

#include//c++标准头文件，可以使用cout,cin等标准库函数

#include//使用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

}

};

struct cmp{

bool operator () (const test t1,const test t2)const{//重载括号运算符

return t1.val

}

};

int main(){

priority_queue,cmp> q;//自定义一个优先级队列q

cout<<"自定义一个优先级队列q: priority_queue,cmp> q"<

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="<

cout<

q.pop();

cout<<"q.top().val="<

cout<

q.pop();

cout<<"q.top().val="<

cout<

q.pop();

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

}

运行结果：

自定义一个优先级队列q: priority_queue,cmp> q

q.top().val=10

q.top().val=7

q.top().val=5

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

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

自定义一个优先级队列q: priority_queue,cmp> q

q.top().val=5

q.top().val=7

q.top().val=10

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

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

是不是很简单呢？

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

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

感谢观看，点个赞吧

推荐链接

 您阅读本篇文章共花了：