Description
补足程序，使得下面程序输出结果是：
1.8
2.4
3.8
4.9
8.8
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <vector>
using namespace std;
int main()
{
// Your Code Here
q.push(2.4);
q.push(3.8);
q.push(1.8);
q.push(4.9);
cout << q.top()<<endl;
q.pop();
cout << q.top()<<endl;
q.pop();
cout << q.top()<<endl;
q.pop();
q.push(8.8);
while(! q.empty()) {
cout << q.top() << endl;
q.pop();
}
return 0;
}
解法如下：
/* 调用 STL 库内的 priority_queue 类 */
priority_queue<float, vector<float>, greater<float> > q;
自己实现一个简单的 priorty_queue，代码如下：
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <vector>
using namespace std;
template<typename T, typename _Comp = less<T> >
class Priority_queue
{
private:
vector<T> data;
_Comp comp;
public:
void push( T t ){
data.push_back(t);
push_heap( data.begin(), data.end(), comp);
}
void pop(){
pop_heap( data.begin(), data.end(), comp);
data.pop_back();
}
T top() { return data.front(); }
bool empty() { return data.empty(); }
};
int main()
{
Priority_queue<float, greater<float> > q;
q.push(2.4);
q.push(3.8);
q.push(1.8);
q.push(4.9);
cout << q.top()<<endl;
q.pop();
cout << q.top()<<endl;
q.pop();
cout << q.top()<<endl;
q.pop();
q.push(8.8);
while(! q.empty()) {
cout << q.top() << endl;
q.pop();
}
return 0;
}