我如何创buildMin stl priority_queue？
默认的stl优先级队列是最大的一个（Top函数返回最大的元素）。
为简单起见，说这是一个int值的优先级队列。
使用std::greater作为比较函数：
std::priority_queue<int, std::vector<int>, std::greater<int> > my_min_heap;
一种方法是定义一个合适的比较器，在普通优先级队列上进行操作，使其优先级相反：
#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的实现使用优先级队列的一些例子。
priority_queue的第三个模板参数是比较器。 将其设置为使用greater 。
例如
std::priority_queue<int, std::vector<int>, std::greater<int> > max_queue;
你需要#include <functional>为std::greater 。
在C ++ 11中，你也可以为了方便创build一个别名：
template<class T> using min_heap = priority_queue<T, std::vector<T>, std::greater<T>>;
像这样使用它：
min_heap<int> my_heap;
你可以用多种方式来做到这一点：
1.使用greater比较function：
#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.使用自定义结构或类，可以按任意顺序使用priority_queue。 假设我们想根据他们的工资按照降序sorting，如果按年龄sorting，
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; }
-
运算符重载可以得到相同的结果：
struct people { int age,salary; bool operator< (const people & p)const { if(salary==p.salary) { return age>p.age; } else { return salary>p.salary; } }};主要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; }
解决这个问题的一种方法是，将priority_queue中每个元素的负数都推下去，这样最大的元素将成为最小的元素。 在popup操作时，取每个元素的否定。
#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(); } }
基于以上所有的答案，我创build了一个示例代码，用于如何创build优先队列。 注意：它适用于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; }
以上代码的输出
Enter number of elements N = 4 33 | 535 49 | 411 411 | 49 535 | 33
我们可以用几种方法做到这一点。
使用模板比较器参数
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; }
使用使用的定义的格子类
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; }
