欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

STL源码分析-heap部分

程序员文章站 2022-06-03 08:39:58
...

heap部分属于序列式容器一章

但是heap并不属于STL容器组件,其帮助于priority queue.

priority queue运行用户用任何次序将任何元素推入容器内,但取出时一定是从数值最高的元素开始取,binary max heap具有这样的特性,适合作为priority queue.底层机制。

若使用list作为priority queue底层机制,元素的插入操作可享常数时间,但是要找到list中的极值,要对整个list遍历。时间过长。

binary heap就是一种完全二叉树。也就是整颗树除了最底层的叶节点之外,是填满的,比如如下:

STL源码分析-heap部分


array表达式:ABCDEFGHIJ

由于完全二叉树 内没有任何节点漏洞,这带来一个极大的好处:可以利用array来存储所有节点。

也就是说某个节点位于array的i处时,左子节点位于2i处,右子节点位于2i+1处,父节点位于i/2处。通过这种简单的位置规则,array可以轻易实现出完全二叉树。这种利用array

表述tree的方式,成为隐式表述法

但array的缺点是无法动态改变大小,而heap却需要,因此用vector代替array是更好的选择



heap分为max-heap和min-heap两种,前者每个节点的键值大于等于其子节点键值,也就是从大到小排列,后者则是从小到大。因此max-heap的最大值在根节点,并总是位于底层vector的起头处。STL提供的是max-heap。因此只对max-heap进行分析。



heap算法


push_heap算法

功能:插入一个新元素


为了满足完全二叉树的条件,新加入的元素一定要放在最下一层作为叶节点,并填补在由左至右的第一个空格,也就是插入在vector的end()处。然后为了满足max-heap的条件,也就是每个节点大于等于其子节点的键值,执行一个上溯(percolate up)程序:将新节点与父节点比较,若比父节点大,就对换位置,如此一致上溯,知道不需对换或者根节点为止。



pop_heap算法

功能:将最大值取走


最大值必然在根节点,pop操作取走根节点(其实是摄至底部容器vector的尾端节点)后,为了满足完全二叉树,必须割舍最下层最右边的叶节点,并将其值重新安插至max-heap。

执行下溯程序:将空间节点与其较大子节点对调,并持续下放直到叶节点为止,然后将割舍的元素值设给这个已到达叶层的空洞节点,再执行一次上溯程序,即可。



sort_heap算法

功能:将heap排序,由小到大


既然每次pop_heap可获得heap键值最大的元素,如果持续对heap执行pop操作,能够得到一个递增序列。因为pop_heap会将最大元素放在最尾端。因此是递增序列。

注意:排序过后,原来的heap不是一个合法的heap了。



make_heap算法

功能:将现有的数据转化为一个heap,主要依据就是完全二叉树的隐式表述。



在实际程序中,要对一个vector(int) A进行排序,可以利用make_heap先将A转化为一个合法的heap,然后利用sort_heap将heap进行从小到大排序即可:


vector<int> A;        
make_heap(A.begin(), A.end());
sort_heap(A.begin(), A.end());






相关标签: stl heap