首页 > 编程语言 > 详细

【算法学习】老算法,新姿势,STL——Heap

时间:2017-06-20 00:07:41      阅读:63      评论:0      收藏:0      [点我收藏+]

标签:内存   str   关系   priority   bug   普通   数组   关于   cto   

“堆”是一个大家很熟悉的数据结构,它可以在\(O(log\;n)\)的时间内维护集合的极值。

这都是老套路了,具体的内部实现我也就不谈了。

我一般来说,都是用queue库中的priority_queue,也就是STL的优先队列来实现堆的,然而最近我发现了一个新的STL容器,它相对优先队列有着更小的常数和更方便的操作。

它就是heap,就是堆。

关于heap,STL提供了4个函数,它们都定义于algorithm库中。它们分别是:

sort一样,其中_First_Last都是头,尾指针或迭代器(对应vector或queue),而_Cmp表示了元素间的大小关系函数。

类似sort,堆中的元素是[_First, _Last)的区间,若内存不连续,也至少要是可随机访问的迭代器(如vector)。

其中_Cmp不是必要的。

还需注意这些函数维护的均是大根堆(即父亲值比孩子大的堆,也称最大堆)。

建立堆:

make_heap(_First, _Last, _Cmp)

在堆中添加元素:

push_heap(_First, _Last, _Cmp)

要先添加元素,再调用函数。

在堆中删除元素:

pop_heap(_First, _Last, _Cmp)

要先调用函数,再删除(不删也可以,只要保证不会出现内存泄漏或者其它bug)。

堆排序:

sort_heap(_First, _Last, _Cmp)

排完序,就像普通的sort一样了,变成有序数组了。不再具有堆的性质。

咚咚咚,代码以后再贴

【算法学习】老算法,新姿势,STL——Heap

标签:内存   str   关系   priority   bug   普通   数组   关于   cto   

原文:http://www.cnblogs.com/PinkRabbit/p/7051057.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号