普通的队列是一种先进先出的数据结构，元素在队列尾追加，在队列头删除。优先队列是个具有优先级的队列，用”堆”来实现的。
在优先队列中，任何时刻，队首元素一定是当前队列中优先级最高（优先值最大）的那一个（大根堆），也可以是最小的那一个（小根堆）。可以不断往优先队列中添加某个优先级的元素，也可以不断弹出优先级最高的那个元素，每次操作其会自动调整结构，始终保证队首元素的优先级最高。
一、优先队列的原理及使用
priority_queue: 在优先队列中，优先级高的元素先出队列，并不是先进先出。
priority_queue<1,2,3>模板声明带有三个参数：
1 数据类型，
2 保存数据的容器，
3 元素比较方式。
数据的容器必须是用数组实现的容器，比如 vector, deque，STL里面默认用的是vector。如果把后面两个参数缺省的话，优先队列就是大顶堆，队头元素最大。priority_queue 默认按照从小到大排列，top()函数返回的是最大值。 如果使用参数greater<>，则数据从大到小排列，那么top()函数返回最小值，队头元素最小。
注意：priority_queue<1,2,3> 如果使用了第3个参数，那第2个参数（用作保存数据的容器）就不能省。
priority_queue<int> pq;//默认是大顶堆，top()返回最大值
priority_queue<int, greater<> > pq;//写法错误，不能省第二个参数
priority_queue<int,vector<int>,greater<int> > pq;//top()返回最小值
//假设node是结构体：
priority_queue<node> pq;//如果数据类型是自定义类型，要重载小于号
priority_queue<node,vector<node>,greater<node> > pq;//要重载大于号二、基本操作
优先队列在头文件#include<queue> 中，定义和常用操作如下。优先队列的时间复杂度为O(logn)，n为队列中元素的个数，其存取都需要时间。
priority_queue<int> a;//声明一个整型优先队列,默认是大根/大顶堆
empty( ) //判断一个队列是否为空
pop( ) //删除队顶元素
push( ) //加入一个元素
size( ) //返回优先队列中拥有的元素个数
top( ) //返回优先队列的队顶元素三、使用方法举例
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int main(){
int aa[8]={1,2,4,3,8,6,11,14};
priority_queue<int,vector<int>,greater<int> > pq;//小顶堆
for (int i = 0; i < 8; i++) {
pq.push(aa[i]); //向队列中加入元素
}
sort(aa+0, aa+8); //aa排序
for (int i = 0; i < 8; i++)
cout << aa[i] << ' '; //输出1 2 3 4 6 8 11 14
cout<<endl;
for (int i = 0; i < 8; i++){ //输出1 2 3 4 6 8 11 14
cout << pq.top() << ' '; //获取队头元素
pq.pop(); //出队
}
cout<<endl;
priority_queue<int,vector<int>,less<int> > pq2;//大顶堆
for (int i = 0; i < 8; i++) {
pq2.push(aa[i]); //向队列中加入元素
}
for (int i = 0; i < 8; i++){ //输出14 11 8 6 4 3 2 1
cout << pq2.top() << ' '; //获取队头元素
pq2.pop(); //出队
}
return 0;
}在优先队列中使用自定义数据类型，需要重载运算符：
#include<iostream>
#include<queue>
using namespace std;
struct node{
int v,w;
bool operator<(const node &nd) const{//重载小于号
return w<nd.w;
}
};
priority_queue<node> q;
int main(){
q.push({21,2});
q.push({11,3});
q.push({5,7});
q.push({6,1});
while(q.size()){//按w值从大到小出队
cout<<q.top().v<<","<<q.top().w<<endl;
q.pop();
}
return 0;
}#include<iostream>
#include<queue>
using namespace std;
struct node{
int v,w;
bool operator>(const node &nd) const{//重载大于号
return w>nd.w;
}
};
priority_queue<node,vector<node>,greater<node> > q;
int main(){
q.push({21,2});
q.push({11,3});
q.push({5,7});
q.push({6,1});
while(q.size()){//按w值从小到大出队
cout<<q.top().v<<","<<q.top().w<<endl;
q.pop();
}
return 0;
}