c语言优先级队列_对结构体数组进行排序

(34) 2024-07-11 13:01:01

文章目录

  • 一、priority_queue 的概念
  • 二、priority_queue 的基本操作
  • 三、priority_queue 的用法

一、priority_queue 的概念

  1. 普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除,即具有最高级先出 (largest-in,first-out)的行为特征。

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

二、priority_queue 的基本操作

使用STL标准库的优先队列时,应包含头文件:#include <queue>

1、定义

 priority_queue<Type> q; priority_queue<Type, Container, Functional> q; priority_queue <int,vector<int>,greater<int> > q; 升序队列 priority_queue <int,vector<int>,less<int> >q; 降序队列 //注意后面两个“>”不要写在一起,“>>”是右移运算符 

Type为数据类型, Container为保存数据的容器,Functional为元素比较方式。
(Container必须是用数组实现的容器,比如vector,deque等等,但不能用 list。使用基本数据类型时,即不写后两个参数,那么STL容器默认用的是vector,比较方式默认用operator<,也就是大顶堆,队头元素最大。)

2、基本操作

 q.empty() 如果队列为空,则返回true,否则返回false q.size() 返回队列中元素的个数 q.pop() 删除队首元素,但不返回其值 q.top() 返回具有最高优先级的元素值,但不删除该元素 q.push(item) 在基于优先级的末尾插入新元素 

注意: 优先队列没有 q.back() 操作

三、priority_queue 的用法

1、基本用法

#include<iostream> #include <queue> using namespace std; int main(){ 
    //对于基础类型 默认是大顶堆,降序队列  priority_queue<int> q1; //等同于 priority_queue<int, vector<int>, less<int> > a; // 这里一定要有空格,不然成了右移运算符↓ priority_queue<int, vector<int>, greater<int> > q2; //小顶堆,升序队列  priority_queue<string> q3; for(int i=0; i<5; i++){ 
    q1.push(i); q2.push(i); } while(!q1.empty()){ 
    //输出大顶堆  cout<<q1.top()<<' '; q1.pop(); } cout<<endl; while(!q2.empty()){ 
    //输出小顶堆  cout<<q2.top()<<' '; q2.pop(); } cout<<endl; q3.push("abc"); q3.push("abcd"); q3.push("cbd"); while (!q3.empty()){ 
    //输出字符串大顶堆  cout<<q3.top()<<' '; q3.pop(); } cout<<endl; return 0; } 

输出结果:
c语言优先级队列_对结构体数组进行排序 (https://mushiming.com/)  第1张

2、pari<Type, Type>类型

先比较第一个元素,如果第一个相等则比较第二个

#include <iostream> #include <queue> #include <vector> using namespace std; int main(){ 
    priority_queue<pair<int, int> > q1; priority_queue<pair<string, string>, vector<pair<string, string> >, greater<pair<string, string> > > q2; pair<int, int> a1(1, 2); pair<int, int> a2(1, 3); pair<int, int> a3(2, 5); q1.push(a1); q1.push(a2); q1.push(a3); pair<string, string> b1("zf", "akl"); pair<string, string> b2("acd", "azkl"); pair<string, string> b3("acd", "ab"); q2.push(b1); q2.push(b2); q2.push(b3); while(!q1.empty()){ 
    cout<<q1.top().first<<' '<<q1.top().second<< '\n'; q1.pop(); } while(!q2.empty()){ 
    cout<<q2.top().first<<' '<<q2.top().second<< '\n'; q2.pop(); } } 

输出结果:
c语言优先级队列_对结构体数组进行排序 (https://mushiming.com/)  第2张

3、自定义类型

方法1: 重载 operator< ,返回true时,说明左边形参的优先级低于右边形参

#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){ 
    //返回true时,说明a的优先级低于b if( a.x== b.x ) //x相等时,y大的优先级低(y小的Node排在队前) return a.y> b.y; return a.x> b.x; //x值较大的Node优先级低(x小的Node排在队前) } 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; } 

输出结果:
c语言优先级队列_对结构体数组进行排序 (https://mushiming.com/)  第3张
注意: 自定义类型重载operator<后,声明对象时就可以只带一个模板参数。但此时不能像基本类型那样声明 priority_queue<Node, vector<Node>, greater<Node> >,因为greater<Node>没有定义。

如果想用这种方法定义 priority_queue<Node, vector<Node>, greater<Node> > 则要重载 operator > ,将方法2。

方法2: 重载 operator> ,返回的是小顶堆。但一般很少这样用,更多的是重载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 ){ 
    //返回true,a的优先级大于b if(a.x== b.x) //x相同时,y大的排在队前部 return a.y> b.y; return a.x> b.x; //x大的排在队前部; } int main(){ 
    priority_queue<Node,vector<Node>,greater<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; } 

输出结果:
c语言优先级队列_对结构体数组进行排序 (https://mushiming.com/)  第4张

方法3: 重写仿函数,返回值排序与方法1、方法2相同,都是小顶堆。

#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) { 
   } }; struct cmp{ 
    //重写的仿函数 //返回true时,a的优先级低于b的优先级(a排在b的后面) bool operator() ( Node a, Node b ){ 
    //默认是less函数 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(); } return 0; } 

输出结果:
c语言优先级队列_对结构体数组进行排序 (https://mushiming.com/)  第5张

THE END

发表回复