今天小编在水昨天考试题题解的时候,突然发现了 STL 自带的手写堆函数,本来以为优先队列已经够了,但是没想到这些函数居然折磨好用,下面快和小编一起来看一看吧~
前言这些函数位于 <functional> 头文件中,不过当然 <bits/stdc++.h> 也是没问题的。
除了普通的数组,结构体建堆也是没有问题的,但需要重载运算符和使用 vector<>()。即使用了 vector<>(),效率也是比 priority_queue<>() 优秀的。
以下的数组均以 q[0] 储存堆大小。
建堆函数原型: make_heap(_RAIter,_RAIter,_Compare)
该函数用于把一个可迭代容器变成一个满足堆性质的序列,默认是大顶堆。时间复杂度为从下向上建堆的 \(O(n)\)。
它有三个参数,前两个是容器的开始元素迭代器和结束元素迭代器(同样是左闭右开)。第三个参数用于生成小根或大根堆,分别是 greater<>() 和 less()<>,默认是大根堆。
注意,如果使用了第三个参数,以下其他所有函数都需要使用同样的参数。
for(int i=1;i<=5;i++) q[++q[0]]=i; make_heap(q+1,q+q[0]+1); for(int i=1;i<=5;i++) printf("%d ",q[i]);OUTPUT:
5 4 3 1 2
函数原型:pop_heap(_RAIter,_RAIter,_Compare)
参数意义同上。该函数用于将堆的第一个元素与最后一个元素交换位置,然后针对前 \(n-1\) 个元素调用 make_heap() 函数,看似好像比较慢,但实际上最坏的时间复杂度约是 \(O(2\log n)\)。
注意本函数只是将元素交换位置,所以真正删除需要 q[0]--,vector 的话就是 pop_back()。
for(int i=1;i<=5;i++) printf("%d ",q[i]); puts(""); pop_heap(q+1,q+q[0]+1); for(int i=1;i<=5;i++) printf("%d ",q[i]); puts("");OUTPUT:
5 4 3 1 2
4 2 3 1 5
函数原型:push_heap(_RAIter,_RAIter,_Compare)
参数意义同上。用于把数据插入到堆中。时间复杂度最坏 \(O(\log n)\)
在使用改函数之前,请确保要插入的数据被加入到容器末尾,如 vector 就是 push_back()。
for(int i=1;i<=5;i++){ q[++q[0]]=i; push_heap(q+1,q+q[0]+1); } for(int i=1;i<=5;i++) printf("%d ",q[i]);OUTPUT:
5 4 2 1 3
当然,先 make_heap 之后再 push_heap 也是可以的,这里不再赘述。
堆排序函数原型:sort_heap(_RAIter,_RAIter,_Compare)
参数意义同上。此函数会将满足堆性质的序列依据大根堆或小根堆排序,排序后,序列将失去堆的性质。时间复杂度 \(O(n\log n)\)。
注意大根堆将变成一个递增序列,小根堆将变成一个递减序列。
请确保在排序前序列满足堆的性质,否则会报错。
不过这个用的应该不多,不如直接 sort 呢。
for(int i=1;i<=5;i++) q[++q[0]]=i; make_heap(q+1,q+q[0]+1); for(int i=1;i<=5;i++) printf("%d ",q[i]); puts(""); sort_heap(q+1,q+q[0]+1); for(int i=1;i<=5;i++) printf("%d ",q[i]); puts("");OUTPUT:
5 4 3 1 2
1 2 3 4 5
这两个代码分别用优先队列和这些函数插入和删除 \(10^6\) 个元素。
优先队列:
priority_queue<int> q; for(int i=1;i<=1e6;i++) q.push(i); for(int i=1;i<=1e6;i++) q.pop();数组:
for(int i=1;i<=1e6;i++){ q[++q[0]]=i; push_heap(q+1,q+q[0]+1); } for(int i=1;i<=1e6;i++){ pop_heap(q+1,q+q[0]+1); q[0]--; }大家都能看出来区别。
所以,在没有增加太多代码量的同时,我们做到了手写堆的效果,小编不禁直呼爷爱了。
总结所以,如果有优先队列卡常卡不过去的情况下还不想手写堆,可以试试这些函数。
当然,在开启 O2 优化的情况下,两者的差距还是不大的,毕竟理论时间复杂度是一样的。
最后来个封装好 push 和 pop 的“手写“大根堆:
#include <functional> struct PRIORITY_QUEUE{ int q[maxn]; inline void Push(int x){ q[q[0]++]=x; push_heap(q+1,q+q[0]+1); } inline void Pop(int x){ pop_heap(q+1,q+q[0]+1); q[0]--; } inline int Size(){ return q[0]; } inline bool Empty(){ return !q[0]; } }q;