学步园

priority_queue 调用 STL里面的 make_heap(), pop_heap(), push_heap() 算法
实现，也算是堆的另外一种形式。

先写一个用 STL 里面堆算法实现的与真正的STL里面的 priority_queue  用法相
似的 priority_queue， 以加深对 priority_queue 的理解

#include <iostream><br /> #include <algorithm><br /> #include <vector><br /> using namespace std;<br /> class priority_queue<br /> {<br /> private:<br /> vector<int> data;</p> <p> public:<br /> void push( int t ){<br /> data.push_back(t);<br /> push_heap( data.begin(), data.end());<br /> }</p> <p> void pop(){<br /> pop_heap( data.begin(), data.end() );<br /> data.pop_back();<br /> }</p> <p> int top() { return data.front(); }<br /> int size() { return data.size(); }<br /> bool empty() { return data.empty(); }<br /> };</p> <p>int main()<br /> {<br /> priority_queue test;<br /> test.push( 3 );<br /> test.push( 5 );<br /> test.push( 2 );<br /> test.push( 4 );</p> <p> while( !test.empty() ){<br /> cout << test.top() << endl;<br /> test.pop(); }</p> <p> return 0;<br /> } 

STL里面的 priority_queue 写法与此相似，只是增加了模板及相关的迭代器什么的。

priority_queue 对于基本类型的使用方法相对简单。
他的模板声明带有三个参数，priority_queue<Type, Container, Functional>
Type 为数据类型， Container 为保存数据的容器，Functional 为元素比较方式。
Container 必须是用数组实现的容器，比如 vector, deque 但不能用 list.
STL里面默认用的是 vector. 比较方式默认用 operator< , 所以如果你把后面俩个
参数缺省的话，优先队列就是大顶堆，队头元素最大。
看例子