priority_queue调用 STL里面的 make_heap(), pop_heap(), push_heap() 算法实现&＃xff0c;也算是堆的另外一种形式。先写一个用 STL 里面堆算法实现的与真正的STL里面的 priority_queue用法相似的priority_queue&＃xff0c; 以加深对 priority_queue 的理解
#include #include #include using namespace std;class priority_queue{ private: vector<int> data; public: void push( int t ){ data.push_back(t); push_heap( data.begin(), data.end()); } void pop(){ pop_heap( data.begin(), data.end() ); data.pop_back(); } int top() { return data.front(); } int size() { return data.size(); } bool empty() { return data.empty(); }};int main(){ priority_queue test; test.push( 3 ); test.push( 5 ); test.push( 2 ); test.push( 4 ); while( !test.empty() ){ cout < test.pop(); } return 0;} |
priority_queue 对于基本类型的使用方法相对简单。他的模板声明带有三个参数:
priority_queue
其中Type 为数据类型&＃xff0c; Container 为保存数据的容器&＃xff0c;Functional 为元素比较方式。
Container 必须是用数组实现的容器&＃xff0c;比如 vector, deque 但不能用 list.
STL里面默认用的是 vector. 比较方式默认用 operator<, 所以如果你把后面俩个参数缺省的话&＃xff0c;
优先队列就是大顶堆&＃xff0c;队头元素最大。
#include #include using namespace std;int main(){ priority_queue<int> q; for( int i&＃61; 0; i<10; &＃43;&＃43;i ) q.push( rand() ); while( !q.empty() ){ cout < q.pop(); } getchar(); return 0;} |
STL里面定义了一个仿函数 greater<>&＃xff0c;对于基本类型可以用这个仿函数声明小顶堆
#include #include using namespace std;int main(){ priority_queue<int, vector<int>, greater<int> > q; for( int i&＃61; 0; i<10; &＃43;&＃43;i ) q.push( rand() ); while( !q.empty() ){ cout < q.pop(); } getchar(); return 0;} |
#include #include using namespace std;struct Node{ int x, y; Node( int a&＃61; 0, int b&＃61; 0 ): x(a), y(b) {}};bool operator<( Node a, Node b ){ if( a.x&＃61;&＃61; b.x ) return a.y> b.y; return a.x> b.x; }int main(){ priority_queue for( int i&＃61; 0; i<10; &＃43;&＃43;i ) q.push( Node( rand(), rand() ) ); while( !q.empty() ){ cout < q.pop(); } getchar(); return 0;} |
但此时不能像基本类型这样声明
priority_queue
原因是 greater
#include #include using namespace std;struct Node{ int x, y; Node( int a&＃61; 0, int b&＃61; 0 ): x(a), y(b) {}};struct cmp{ bool operator() ( Node a, Node b ){ if( a.x&＃61;&＃61; b.x ) return a.y> b.y; return a.x> b.x; }};int main(){ priority_queue for( int i&＃61; 0; i<10; &＃43;&＃43;i ) q.push( Node( rand(), rand() ) ); while( !q.empty() ){ cout < q.pop(); } getchar(); return 0;} //以上代码实现的是一个小顶堆 |
转载:http://blog.chinaunix.net/space.php?uid&＃61;533684&do&＃61;blog&cuid&＃61;2615612
ps:如果重载operator > 可直接使用priority_queue
poj 2442
题目&＃xff1a;http://poj.org/problem?id&＃61;2442
代码&＃xff1a;
View Code 1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6 bool cmp(int a,int b)
7 {
8 return a<b;
9 }
10 int main()
11 {
12 int m,n,t;
13 cin>>t;
14 int num1[2010];
15 int num2[2010];
16 int i,j,k,s;
17 priority_queue<int,deque<int>,less<int> > que;
18 while(t--)
19 {
20 cin>>m>>n;
21 for(i&＃61;0;i
22 {
23 cin>>num1[i];
24 }
25 sort(num1,num1&＃43;n,cmp);
26 for(i&＃61;1;i
27 {
28 for(j&＃61;0;j
29 {
30 cin>>num2[j];
31 que.push(num1[0]&＃43;num2[j]);
32 }
33 sort(num2,num2&＃43;n,cmp);
34 for(k&＃61;1;k
35 {
36 for(s&＃61;0;s
37 {
38 if(num1[k]&＃43;num2[s]>que.top())
39 break;
40 que.pop();
41 que.push(num1[k]&＃43;num2[s]);
42 }
43 }
44 for(k&＃61;0;k
45 {
46 num1[n-k-1]&＃61;que.top();
47 que.pop();
48 }
49 }
50 for(i&＃61;0;i
51 {
52 printf("%d",num1[i]);
53 if(i&＃61;&＃61;n-1)
54 printf("\n");
55 else
56 printf(" ");
57 }
58 }
59 return 0;
60 }
poj 1442
题目&＃xff1a;http://poj.org/problem?id&＃61;1442
利用的是维护两个堆的思想&＃xff0c;从1~i-1建立大顶堆&＃xff0c;i~k建立小顶堆&＃xff0c;k是当前时刻ADD个数&＃xff0c;堆利用优先队列实现。。。
View Code 1 #include
2 #include
3 #include
4 using namespace std;
5 int main()
6 {
7 priority_queue<int>que;
8 priority_queue<int,vector<int>,greater<int> >q;
9 int a[30010];
10 int n,i,m;
11 cin>>m>>n;
12 for(i&＃61;0;i
13 {
14 scanf("%d",&a[i]);
15 }
16 int uu&＃61;0;
17 int h&＃61;0;
18 int t,u;
19 for(i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
20 {
21 scanf("%d",&t);
22 u&＃61;t-h;
23 while(u)
24 {
25 q.push(a[uu]);
26 uu&＃43;&＃43;;
27 if(!que.empty()&&que.top()>q.top())
28 {
29 que.push(q.top());
30 q.pop();
31 q.push(que.top());
32 que.pop();
33 }
34 u--;
35 }
36 h&＃61;t;
37 cout<
38 que.push(q.top());
39 q.pop();
40 }
41 return 0;
42 }
京公网安备 11010802041100号