ฅ(๑˙o˙๑)ฅ 大家好, 欢迎大家光临我的博客：面向阿尼亚学习
算法学习笔记系列持续更新中~

---

---

一、前言

优先队列和队列特性不同：按优先级排序 和 获取
既然是队列那么先要包含头文件#include <queue>, 他和queue不同的就在于我们可以自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队

优先队列具有队列的所有特性，包括基本操作，只是在这基础上添加了内部的一个排序，它本质是一个堆实现的
所以它的功能强大在哪里呢？
四个字：自动排序

---

二、priority_queue的初始化

这里是默认的优先队列（非结构体结构）

注意：默认是大根堆！！！

​大根堆：priority_queue <类型> 变量名;

​小根堆：priority_queue <类型,vecotr <类型>,greater <类型> > 变量名

如：
priority_queue<int, vector<int>, less<int> >s;//less表示按照递减(从大到小)的顺序插入元素
priority_queue<int, vector<int>, greater<int> >s;//greater表示按照递增（从小到大）的顺序插入元素

//注意后面两个“>”不要写在一起，“>>”是右移运算符

默认优先队列样例

#include <iostream>
#include<queue>
using namespace std;
//priority_queue <int> q;默认大根堆 
priority_queue<int, vector<int>, less<int> >q1; //大根堆 
priority_queue<int, vector<int>, greater<int> >q2;//小根堆 
int a[5]={9,5,2,7,1}; 
int main()
{
    for(int i=0;i<5;i++)
   {
   	q1.push(a[i]);
   	q2.push(a[i]);
   }
    //大根堆 
     cout<<"大根堆:";
	while(!q1.empty())
	{
	cout<<q1.top()<<" ";
	q1.pop();
    }	
    cout<<endl;
    //小根堆
    cout<<"小根堆:";
    while(!q2.empty())
	{
	cout<<q2.top()<<" ";
	q2.pop();
    }	
}

输出

大根堆:9 7 5 2 1
小根堆:1 2 5 7 9

三、priority_queue的常用函数

​

​    size(); 这个堆的长度

​    empty(); 返回这个堆是否为空

​    push();往堆里插入一个元素

​    top(); 返回堆顶元素

​    pop(); 弹出堆顶元素

​    注意：堆没有clear函数！！！
    注意：堆没有back()函数！！！

四、priority_queue 自定义结构体初始化

自定义结构体实现大根堆，小根堆

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

struct cmp1 {
	bool operator ()( int a ,int b ) {
		return a<b;
	}
};
struct cmp2 {
	bool operator ()( int  a ,int b ) {
		return a>b;
	}
};
int a[5]={9,5,2,7,1}; 
int  main() {

	   priority_queue < int , vector<int> , cmp1  > q1;//从大到小 
	   priority_queue < int , vector<int> , cmp2  > q2;//从小到大 

	  for(int i=0;i<5;i++)
   {
   	q1.push(a[i]);
   	q2.push(a[i]);
   }

 //大根堆 
     cout<<"大根堆:";
	while(!q1.empty())
	{
	cout<<q1.top()<<" ";
	q1.pop();
    }	
    cout<<endl;
    //小根堆
    cout<<"小根堆:";
    while(!q2.empty())
	{
	cout<<q2.top()<<" ";
	q2.pop();
    }	
	return 0;
}

输出
大根堆:9 7 5 2 1
小根堆:1 2 5 7 9

---

自定义结构体实现两个成员x和y，按x小者优先

#include <iostream>
#include<queue>
using namespace std;
struct node
{
	int x,y;
	bool operator < (const node & a) const
	{
		return x<a.x;//大根 
	//	return x>a.x;//小根 
	}
};
priority_queue <node> q;
int a[5]={2,5,1,6,4};
int b[5]={9,8,2,1,3};
int main()
{
	node t;
	for(int i=0;i<5;i++)
	{
		t.x=a[i];
		t.y=b[i];
		q.push(t);
	}
	while(!q.empty())
	{
		node m=q.top(); q.pop();
		cout<<m.x<<" "<<m.y<<endl;
	}
}

输出
6 1
5 8
4 3
2 9
1 2

---

自定义结构体先按x升序，x相等时，再按y升序

#include <iostream>
#include <queue>
using namespace std;
struct Node{
    int x, y;
    Node( int a= 0, int b= 0 ):
      x(a), y(b) {}
};
struct cmp{//重写的仿函数
    bool operator() ( Node a, Node b ){//默认是less函数
        //返回true时，a的优先级低于b的优先级（a排在b的后面）
        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()%10, rand()%10 ) );
    
    while( !q.empty() ){
        cout << q.top().x << ' ' << q.top().y << endl;
        q.pop();
    }
    return 0;
}

输出
0 4
1 1
2 5
4 2
4 9
5 5
6 7
7 1
7 1
8 8

---

更深一点的，还在学习~

---

最后

莫言真理无穷尽，寸进自有寸进欢