优先队列priority

优先队列priority_queue应用

不讲概念！！只说用法！！！！！
优先队列 priority_queue 换种话来说就是堆，只可以从中取到最大或者最小的值，所以说，只维护堆顶。它使用less（）作为比较函数，即元素的优先级按照从大到小的顺序排列。如果需要按照从小到大的顺序排列，可以使用greater（）作为比较函数。也就是说，如果我要取最大值，那么我就不管（使用其默认的less），我要取最小值，那么就要使用greater()
上图：
在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
int main()
{priority_queue<int,vector<int>,greater<int>>pq;for(int i=0;i<5;i++){int x;cin>>x;pq.push(x);}while(!pq.empty()){cout<<pq.top()<<'\n';pq.pop();}return 0;}

如果我们使用greater的话那么每次就会找到这个堆的最小值，我们可以用这个方法找出数组或者vector容器中的最大最小值，或者给数组或者容器排序。
如图：
最小值：
在这里插入图片描述
代码如下：

#include<bits/stdc++.h>
using namespace std;
int main()
{priority_queue<int,vector<int>,greater<int>>pq;priority_queue<int,vector<int>,greater<int>>pq2;int n;cin>>n;//代表初始数组的大小 int arr[n];vector<int>v;//给数组赋值 for(int i=0;i<n;i++){cin>>arr[i];pq.push(arr[i]);}
//---------------------------------------------------------------------------//给vector赋值 for(int i=0;i<n;i++){int x;cin>>x;v.push_back(x);pq2.push(v[i]);}//---------------------------------------------------------------------------//通过优先队列找出数组中的最小值int min1=pq.top(),min2=pq2.top();cout<<min1<<" "<<min2<<'\n';return 0;}

最大值：
在这里插入图片描述
代码如下：

#include<bits/stdc++.h>
using namespace std;
int main()
{priority_queue<int,vector<int>,less<int>>pq;priority_queue<int,vector<int>,less<int>>pq2;int n;cin>>n;//代表初始数组的大小 int arr[n];vector<int>v;//给数组赋值 for(int i=0;i<n;i++){cin>>arr[i];pq.push(arr[i]);}
//---------------------------------------------------------------------------//给vector赋值 for(int i=0;i<n;i++){int x;cin>>x;v.push_back(x);pq2.push(v[i]);}//---------------------------------------------------------------------------//通过优先队列找出数组中的最大值int max1=pq.top(),max2=pq2.top();cout<<max1<<" "<<max2<<'\n';return 0;}

排序(由大到小）：在这里插入图片描述
代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{priority_queue<int,vector<int>,greater<int>>pq;priority_queue<int,vector<int>,greater<int>>pq2;int n;cin>>n;//代表初始数组的大小 int arr[n];vector<int>v;//给数组赋值 for(int i=0;i<n;i++){cin>>arr[i];pq.push(arr[i]);}
//---------------------------------------------------------------------------//给vector赋值 for(int i=0;i<n;i++){int x;cin>>x;v.push_back(x);pq2.push(v[i]);}//---------------------------------------------------------------------------//排序vector<int>r1,r2;while(!pq.empty()){r1.push_back(pq.top());pq.pop();}cout<<"r1:";for(auto &e : r1) cout<<e<<" ";cout<<'\n';while(!pq2.empty()){r2.push_back(pq2.top());pq2.pop();}cout<<"r2:";for(auto &e : r2) cout<<e<<" ";cout<<'\n';return 0;}

排序（由大到小）：
在这里插入图片描述
代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{priority_queue<int,vector<int>,less<int>>pq;priority_queue<int,vector<int>,less<int>>pq2;int n;cin>>n;//代表初始数组的大小 int arr[n];vector<int>v;//给数组赋值 for(int i=0;i<n;i++){cin>>arr[i];pq.push(arr[i]);}
//---------------------------------------------------------------------------//给vector赋值 for(int i=0;i<n;i++){int x;cin>>x;v.push_back(x);pq2.push(v[i]);}//---------------------------------------------------------------------------//排序vector<int>r1,r2;while(!pq.empty()){r1.push_back(pq.top());pq.pop();}cout<<"r1:";for(auto &e : r1) cout<<e<<" ";cout<<'\n';while(!pq2.empty()){r2.push_back(pq2.top());pq2.pop();}cout<<"r2:";for(auto &e : r2) cout<<e<<" ";cout<<'\n';return 0;}