• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

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

开发技术 开发技术 5天前 9次浏览

今天小编在水昨天考试题题解的时候,突然发现了 STL 自带的手写堆函数,本来以为优先队列已经够了,但是没想到这些函数居然折磨好用,下面快和小编一起来看一看吧~

前言

这些函数位于 <functional> 头文件中,不过当然 <bits/stdc++.h> 也是没问题的。

除了普通的数组,结构体建堆也是没有问题的,但需要重载运算符。

以下的数组均以 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(2log 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(nlog 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 优化的情况下,两者的差距还是不大的,毕竟理论时间复杂度是一样的。

最后来个封装好 pushpop 的“手写“大根堆:

#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;

喜欢 (0)