如何创建 Minstl 优先级队列？

使用 std::greater作为比较函数:

std::priority_queue<int, std::vector<int>, std::greater<int> > my_min_heap;

priority_queue的第三个模板参数是比较器。

例如:。

std::priority_queue<int, std::vector<int>, std::greater<int> > max_queue;

std::greater需要 #include <functional>。

一种方法是定义一个合适的比较器，用于对普通优先级队列进行操作，这样它的优先级就会被反转:

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


struct compare
{
bool operator()(const int& l, const int& r)
{
return l > r;
}
};


int main()
{
priority_queue<int,vector<int>, compare > pq;


pq.push(3);
pq.push(5);
pq.push(1);
pq.push(8);
while ( !pq.empty() )
{
cout << pq.top() << endl;
pq.pop();
}
cin.get();
}

它将分别输出1,3,5,8。

给出了通过 STL 和 Sedgewick 的实现使用优先级队列的一些示例 给你。

在 C + + 11中，为了方便起见，你还可以创建一个别名:

template<class T> using min_heap = priority_queue<T, std::vector<T>, std::greater<T>>;

像这样使用它:

min_heap<int> my_heap;

解决这个问题的一种方法是，推出的优先级队列中的每个元素的负数，使最大的元素将成为最小的元素。在进行弹出运算时，取每个元素的否定值。

#include<bits/stdc++.h>
using namespace std;


int main(){
priority_queue<int> pq;
int i;


// push the negative of each element in priority_queue, so the largest number will become the smallest number


for (int i = 0; i < 5; i++)
{
cin>>j;
pq.push(j*-1);
}


for (int i = 0; i < 5; i++)
{
cout<<(-1)*pq.top()<<endl;
pq.pop();
}
}

你可以通过多种方式做到这一点:
1. 使用 greater作为比较函数:

 #include <bits/stdc++.h>


using namespace std;


int main()
{
priority_queue<int,vector<int>,greater<int> >pq;
pq.push(1);
pq.push(2);
pq.push(3);


while(!pq.empty())
{
int r = pq.top();
pq.pop();
cout<<r<< " ";
}
return 0;
}

2.通过改变符号(正数使用减号(-) ，负数使用加号(+))来插入值:

int main()
{
priority_queue<int>pq2;
pq2.push(-1); //for +1
pq2.push(-2); //for +2
pq2.push(-3); //for +3
pq2.push(4);  //for -4


while(!pq2.empty())
{
int r = pq2.top();
pq2.pop();
cout<<-r<<" ";
}


return 0;
}

3. 使用定制结构或类:

struct compare
{
bool operator()(const int & a, const int & b)
{
return a>b;
}
};


int main()
{


priority_queue<int,vector<int>,compare> pq;
pq.push(1);
pq.push(2);
pq.push(3);


while(!pq.empty())
{
int r = pq.top();
pq.pop();
cout<<r<<" ";
}


return 0;
}

4. 使用自定义结构或类，可以按任意顺序使用 Pridery_ queue。 假设，我们希望根据薪水将人们按降序排序，如果根据年龄将他们绑在一起。

    struct people
{
int age,salary;


};
struct compare{
bool operator()(const people & a, const people & b)
{
if(a.salary==b.salary)
{
return a.age>b.age;
}
else
{
return a.salary>b.salary;
}


}
};
int main()
{


priority_queue<people,vector<people>,compare> pq;
people person1,person2,person3;
person1.salary=100;
person1.age = 50;
person2.salary=80;
person2.age = 40;
person3.salary = 100;
person3.age=40;




pq.push(person1);
pq.push(person2);
pq.push(person3);


while(!pq.empty())
{
people r = pq.top();
pq.pop();
cout<<r.salary<<" "<<r.age<<endl;
}

5. 运算符重载亦可得到相同的结果:

   struct people
   {
   int age,salary;
   
   
   bool operator< (const people & p)const
   {
   if(salary==p.salary)
   {
   return age>p.age;
   }
   else
   {
   return salary>p.salary;
   }
   }};
   

   主要功能:

   priority_queue<people> pq;
   people person1,person2,person3;
   person1.salary=100;
   person1.age = 50;
   person2.salary=80;
   person2.age = 40;
   person3.salary = 100;
   person3.age=40;
   
   
   
   
   pq.push(person1);
   pq.push(person2);
   pq.push(person3);
   
   
   while(!pq.empty())
   {
   people r = pq.top();
   pq.pop();
   cout<<r.salary<<" "<<r.age<<endl;
   }
   

基于以上所有答案，我创建了一个示例代码，说明如何创建优先级队列

#include <iostream>
#include <vector>
#include <iomanip>
#include <queue>


using namespace std;


// template for prirority Q
template<class T> using min_heap = priority_queue<T, std::vector<T>, std::greater<T>>;
template<class T> using max_heap = priority_queue<T, std::vector<T>>;


const int RANGE = 1000;


vector<int> get_sample_data(int size);


int main(){
int n;
cout << "Enter number of elements N = " ; cin >> n;
vector<int> dataset = get_sample_data(n);


max_heap<int> max_pq;
min_heap<int> min_pq;


// Push data to Priority Queue
for(int i: dataset){
max_pq.push(i);
min_pq.push(i);
}


while(!max_pq.empty() && !min_pq.empty()){
cout << setw(10) << min_pq.top()<< " | " << max_pq.top() << endl;
min_pq.pop();
max_pq.pop();
}


}




vector<int> get_sample_data(int size){
srand(time(NULL));
vector<int> dataset;
for(int i=0; i<size; i++){
dataset.push_back(rand()%RANGE);
}
return dataset;
}

以上代码的输出

Enter number of elements N = 4


33 | 535
49 | 411
411 | 49
535 | 33