priority_queue优先队列，简单介绍

STL优先队列：priority_queue

STL中的优先队列也是一种队列（queue），但平时我们使用的队列不同的在于我们可以自定义其中数据的优先级, 让优先级高的排在队列前面，可以理解为一个时刻都在排序的队列，如果我们不设置这个优先级别，他会自动默认的把数据大的数字排列在前面。

以下是一些例子：

普通队列：

#include<bits/stdc++.h>
using namespace std;
int main(){
       queue<int> pq;
       for(int i=1;i<=5;i++){
              pq.push(i);
              cout<<"push element "<<i<<endl;
       }
       for(int i=1;i<=5;i++){
              int temp=pq.front();
              pq.pop();
              cout<<"No "<<i<<" element is: "<<temp<<endl;
       }
       return 0;
}

优先队列：

#include<bits/stdc++.h>
using namespace std;
int main(){
       priority_queue<int> pq;
       for(int i=1;i<=5;i++){
              pq.push(i);
              cout<<"push element "<<i<<endl;
       }
       for(int i=1;i<=5;i++){
              int temp=pq.top();
              pq.pop();
              cout<<"No "<<i<<" element is: "<<temp<<endl;
       }
       return 0;
}

由上面的实验可以得验证：

那么作为STL中的一员，priority_queue包含如下的操作：

top          访问队头元素         //这与普通的queue可以用front不同，优先队列没有front操作

empty     队列是否为空

size         返回队列内元素个数

push       插入元素到队尾 (并排序)

emplace 原地构造一个元素并插入队列

pop         弹出队头元素

swap       交换内容

使用方式为：

priority_queue<T, Container, Compare>

STL官方文档中这么介绍其内容：

T

Type of the elements.
Aliased as member type priority_queue::value_type.

Container

Type of the internal underlying container object where the elements are stored.
Its value_type shall be T.
Aliased as member type priority_queue::container_type.

Compare

A binary predicate that takes two elements (of type T) as arguments and returns a bool.
The expression comp(a,b), where comp is an object of this type and a and b are elements in the container, shall return true if a is considered to go before b in the strict weak ordering the function defines.
The priority_queue uses this function to maintain the elements sorted in a way that preserves heap properties(i.e., that the element popped is the last according to this strict weak ordering).
This can be a function pointer or a function object, and defaults to less<T>, which returns the same as applying the less-than operator (a<b).

简单翻译一下就是

1.     T就是Type为数据类型

2.     Container是容器类型，（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector）

3.     Compare是比较方法，类似于sort第三个参数那样的比较方式，对于自定义类型，需要我们手动进行比较运算符的重载。

与sort直接Bool一个函数来进行比较的简单方法不同，Compare需要使用结构体的运算符重载完成，直接bool cmp(int a,int b){     return a>b; } 这么写是无法通过编译的。

Compare不填写则默认升序即大顶堆

STL中赠送的两个less和greater均可直接应用于Compare中

//升序队列

priority_queue <int,vector<int>,greater<int> > q;

//降序队列

priority_queue <int,vector<int>,less<int> >q;

那么我们不使用自带的方法，重载一个比较符来完成小于比较，这样数值越小的数就在了前面。

#include<bits/stdc++.h>
using namespace std;
struct cmp {          //这个比较要用结构体表示
       bool operator()(int &a,int &b) const {
              return a>b;
       }
};
int main() {
       priority_queue<int,vector<int>,cmp> pq;
       for(int i=1; i<=5; i++) {
              pq.push(i);
              cout<<"push element "<<i<<endl;
       }
       for(int i=1; i<=5; i++) {
              int temp=pq.top();
              pq.pop();
              cout<<"No "<<i<<" element is: "<<temp<<endl;
       }
}

马上就要去打ACM了，心慌慌的.....

于是就分享自己的资料出来了