STL--priority_queue（优先队列）

头文件
#include<queue>
基本操作和队列基本操作相同:</queue>

top 访问队头元素
empty 队列是否为空
size 返回队列内元素个数
push 插入元素到队尾 (并排序)
emplace 原地构造一个元素并插入队列
pop 弹出队头元素
swap 交换内容

一：一般用法
定义:

1:priority_queue<int> pq;//默认状态下是大顶堆 
2:priority_queue <int,vector<int>,greater<int> > q;//升序队列，小顶堆
3:priority_queue <int,vector<int>,less<int> >q;//降序队列，大顶堆

应用：
自动排序的容器，可以将容器内的数据自动按照默认或自定义的方式排序
例如：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    priority_queue<int>q;
    int a[10]={11,21,32,819,216,217,418,931,21,-21};
    for(int i=0;i<10;i++)
    {
        q.push(a[i]);
     } 
     while(q.empty()!=true)
     {
         printf("%d ",q.top());
         q.pop();
     }
     return 0;
 }

结果为：
图片说明

二：用pair作为优先队列元素的例子
定义：
priority_queue<pair<int, int> > a;默认大顶堆
//typedef pair<int, int> node_type;将pair结构类型重命名
priority_queue<node_type, vector<node_type>, greater<node_type> > P;//升序队列，小顶堆
priority_queue<node_type, vector<node_type>, less<node_type> > Q;//降序队列，大顶堆
应用:
排序时先对第一个元素进行比较，如果相同则再对第二个元素排序
例如：
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>node_p;
int main()
{
int t=1;
int a[10]={10,41,41,45,97,21,77,37,90,10};
priority_queue<node_p,vector<node_p>,greater<node_p> >q;
for(int i=0;i<10;i++)
{
if(i%2==0)t+=1;
else t-=1;
q.push(make_pair(t,a[i]));
}
while(q.empty()!=true)
{
printf("%d %d\n",q.top().first,q.top().second);
q.pop();
}
return 0;
}
结果为：
图片说明 </node_p></node_p></node_type></node_type></node_type></node_type>

三：采用自定义排序方式排序
一般情况自定义方式：

struct temp{
      bool operator() (int a, int b) 
     {
         if(a*a==b*b)
         return a<b;
        else return a*a < b*b; //大顶堆
     }
};

pair类型的自定义方式

struct temp1{
    bool operator()(node_p a,node_p b)
    {    
        if(a.first==b.first)return a.second<b.second;
        else return a.first>b.first;
    }
};

应用:

#include<bits/stdc++.h>
using namespace std;
int t=1;
int  a[10]={10,-19,-7,-5,9,7,21,17,37,-10};
typedef pair<int,int>node_p;
struct temp{
      bool operator() (int a, int b) 
     {
         if(a*a==b*b)
         return a<b;
        else return a*a < b*b; //大顶堆
     }
};
struct temp1{
    bool operator()(node_p a,node_p b)
    {    
        if(a.first==b.first)return a.second<b.second;
        else return a.first>b.first;
    }
};
//int main()
//{
//    priority_queue<node_p,vector<node_p>,temp1 >q;
//    for(int i=0;i<10;i++)
//    {
//        if(i%2==0)t+=1;
//        else t-=1;
//        q.push(make_pair(t,a[i]));
//     } 
//     while(q.empty()!=true)
//     {
//         printf("%d %d\n",q.top().first,q.top().second);
//         q.pop();
//     }
//     return 0;
// } 
 int main()
 {
     priority_queue<int,vector<int>,temp>q;
     for(int i=0;i<10;i++)
     {
         q.push(a[i]);
     }
     while(q.empty()!=true)
     {
         printf("%d\n",q.top());
         q.pop();
     }
     return 0;
 }

四：采用自定义元素类型以及自定义排序方式
自定义元素类型

  struct tmp1 //运算符重载<
  {
     int x;
      tmp1(int a) {x = a;}
     bool operator<(const tmp1& a) const
    {
         return x < a.x; //大顶堆
     }
 };

应用：

#include <iostream>
#include <queue>
using namespace std;

//方法1
struct tmp1 //运算符重载<
{
    int x;
    tmp1(int a) {x = a;}
    bool operator<(const tmp1& a) const
    {
        return x < a.x; //大顶堆
    }
};

//方法2
struct tmp2 //重写仿函数
{
    bool operator() (tmp1 a, tmp1 b) 
    {
        return a.x < b.x; //大顶堆
    }
};

int main() 
{
    tmp1 a(1);
    tmp1 b(2);
    tmp1 c(3);
    priority_queue<tmp1> d;
    d.push(b);
    d.push(c);
    d.push(a);
    while (!d.empty()) 
    {
        cout << d.top().x << '\n';
        d.pop();
    }
    cout << endl;

    priority_queue<tmp1, vector<tmp1>, tmp2> f;
    f.push(c);
    f.push(b);
    f.push(a);
    while (!f.empty()) 
    {
        cout << f.top().x << '\n';
        f.pop();
    }
}

参考文件c++优先队列(priority_queue)用法详解