我设计了一个优先队列,但它不适用于某些测试用例。优先级队列不能很好地与compare()
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
template <class T1, class T2>
class priorityQueue {
private:
vector<T1> dataContainer;
class Compare {
public:
// Compare two elements .
bool operator()(const T1& a, const T1& b) const {
return a > b;
}
};
public:
priorityQueue(vector<T1>& myV) : dataContainer(myV) {
make_heap(dataContainer.begin(), dataContainer.end(), Compare());
}
bool empty() const { return dataContainer.empty(); }
// get the size of the queue
size_t size() const { return dataContainer.size(); }
// get the element with the highest priority in the queue
T1& top(){ return dataContainer.front();}
// push an element into the qeueu
void enQueue(T1& element) {
dataContainer.push_back(element);
push_heap(dataContainer.begin(), dataContainer.end(), Compare());
}
// pop the element with the highest priority in the qeueu
void deQueue() {
pop_heap(dataContainer.begin(), dataContainer.end(), Compare());
dataContainer.erase(dataContainer.begin());
}
void printQ() {
typename vector<T1>::iterator itr ;
cout << "the priorityQueue is : " << endl ;
for (itr = dataContainer.begin(); itr != dataContainer.end(); ++itr) {
cout << *itr << "\t";
}
cout << endl ;
}
};
int main() {
vector<int> aa;
int a[4] = {5, 8, 3, 2};
aa.assign(a, a+4);
priorityQueue<int, bool> myQ(aa);
myQ.printQ();
return 0;
}
比较类不能改变优先顺序。
a > b
的输出应为2 3 5 8
。
UPDATE的问题已经解决了,感谢
什么是实际输出?在问题中使用“a b”,哪一个? –
对不起,这是一个错字,应该是a> b,输出是2 5 3 8,它可以在linux上运行,应该是8 5 3 2。谢谢。 – user1002288
为什么标记为C? – GManNickG