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

一、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; } 

输出结果：

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(); } } 

输出结果：

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; } 

输出结果：

注意： 自定义类型重载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; } 

输出结果：

方法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; } 

输出结果：