C++ 如何创建 Min stl priority_queue？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2439283/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How can I create Min stl priority_queue?
提问by amitlicht
The default stl priority queue is a Max one (Top function returns the largest element).
默认的 stl 优先级队列是 Max one（Top 函数返回最大元素）。
Say, for simplicity, that it is a priority queue of int values.
为简单起见，假设它是一个 int 值的优先级队列。
回答by James McNellis
Use std::greateras the comparison function:
使用std::greater的比较函数：
std::priority_queue<int, std::vector<int>, std::greater<int> > my_min_heap;
回答by AndyUK
One way would be to define a suitable comparator with which to operate on the ordinary priority queue, such that its priority gets reversed:
一种方法是定义一个合适的比较器来对普通优先级队列进行操作，以便其优先级被反转：
#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();
}
Which would output 1, 3, 5, 8 respectively.
这将分别输出 1、3、5、8。
Some examples of using priority queues via STL and Sedgewick's implementationsare given here.
此处给出了通过 STL 和Sedgewick 的实现使用优先级队列的一些示例。
回答by Peter Alexander
The third template parameter for priority_queueis the comparator. Set it to use greater.
第三个模板参数priority_queue是比较器。将其设置为使用greater.
e.g.
例如
std::priority_queue<int, std::vector<int>, std::greater<int> > max_queue;
You'll need #include <functional>for std::greater.
你需要#include <functional>为std::greater.
回答by Taohidul Islam
You can do it in multiple ways:
1. Using greateras comparison function :
您可以通过多种方式做到这一点：
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. Inserting values by changing their sign (using minus (-) for positive number and using plus (+) for negative number :
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. Using custom structure or class :
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. Using custom structure or class you can use priority_queue in any order. Suppose, we want to sort people in descending order according to their salary and if tie then according to their age.
4. 使用自定义结构或类，您可以按任何顺序使用 priority_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;
}
Same result can be obtained by operator overloading :
struct people { int age,salary; bool operator< (const people & p)const { if(salary==p.salary) { return age>p.age; } else { return salary>p.salary; } }};In main function :
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; }
通过运算符重载可以获得相同的结果：
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; }
回答by mechatroner
In C++11 you could also create an alias for convenience:
在 C++11 中，您还可以为方便起见创建别名：
template<class T> using min_heap = priority_queue<T, std::vector<T>, std::greater<T>>;
And use it like this:
并像这样使用它：
min_heap<int> my_heap;
回答by PAVAN BANSAL
One Way to solve this problem is, push the negative of each element in the priority_queue so the largest element will become the smallest element. At the time of making pop operation, take the negation of each element.
解决这个问题的一种方法是，压入priority_queue中每个元素的负数，这样最大的元素就会变成最小的元素。在做pop操作的时候，取每个元素的否定。
#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();
}
}
回答by ajayramesh
Based on above all answers I created an example code for how to create priority queue. Note: It works C++11 and above compilers
基于以上所有答案，我创建了一个示例代码来说明如何创建优先级队列。注意：它适用于 C++11 及更高版本的编译器
#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;
}
Output of Above code
以上代码的输出
Enter number of elements N = 4
33 | 535
49 | 411
411 | 49
535 | 33
回答by rashedcs
We can do this using several ways.
我们可以使用多种方法来做到这一点。
Using template comparator parameter
使用模板比较器参数
int main()
{
priority_queue<int, vector<int>, greater<int> > pq;
pq.push(40);
pq.push(320);
pq.push(42);
pq.push(65);
pq.push(12);
cout<<pq.top()<<endl;
return 0;
}
Using used defined compartor class
使用已定义的比较器类
struct comp
{
bool operator () (int lhs, int rhs)
{
return lhs > rhs;
}
};
int main()
{
priority_queue<int, vector<int>, comp> pq;
pq.push(40);
pq.push(320);
pq.push(42);
pq.push(65);
pq.push(12);
cout<<pq.top()<<endl;
return 0;
}
