【学习笔记】不会吧不会吧,不会有人还在手写堆吧

今天小编在水昨天考试题题解的时候,突然发现了 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;

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpypdd.html