内容简介:对于支持假定已经是一个
简介
heap
对于支持 RandomAccessIterator
的容器适用。默认构造最大堆。
-
push_heap
- 元素放在末尾,然后
__push_heap
- 元素放在末尾,然后
-
pop_heap
- pop 元素会放在末尾,然后插入末尾的元素
-
make_heap
- [0, n/2) 不断地去
__adjust_heap
- [0, n/2) 不断地去
-
sort_heap
- 不断地调用
pop_heap
- 不断地调用
__push_heap
假定已经是一个 heap
了,新插入的元素在末尾,不断地和它的 parent
比较,如果比
-
__value > *_parent
: 则递归往上找,当前节点替换为其parent
的值 -
__value <= *_parent
: 则停止,找到所要插入的位置,插入元素即可
template <class _RandomAccessIterator, class _Distance, class _Tp> void __push_heap(_RandomAccessIterator __first, _Distance __holeIndex, _Distance __topIndex, _Tp __value) { _Distance __parent = (__holeIndex - 1) / 2; while (__holeIndex > __topIndex && *(__first + __parent) < __value) { *(__first + __holeIndex) = *(__first + __parent); __holeIndex = __parent; __parent = (__holeIndex - 1) / 2; } *(__first + __holeIndex) = __value; }
__adjust_heap
当移除一个元素时,需要找到它的替代元素。不断找左右孩子中较大的:
- 将移除位置不断和它孩子中较大的元素交换,直至到最后的结尾
- 这一步确保从
holeIndex
到下面是满足heap
的顺序结构的
- 这一步确保从
- 然后再把元素插入到末尾
template <class _RandomAccessIterator, class _Distance, class _Tp> void __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, _Distance __len, _Tp __value) { _Distance __topIndex = __holeIndex; _Distance __secondChild = 2 * __holeIndex + 2; while (__secondChild < __len) { if (*(__first + __secondChild) < *(__first + (__secondChild - 1))) __secondChild--; *(__first + __holeIndex) = *(__first + __secondChild); __holeIndex = __secondChild; __secondChild = 2 * (__secondChild + 1); } if (__secondChild == __len) { *(__first + __holeIndex) = *(__first + (__secondChild - 1)); __holeIndex = __secondChild - 1; } __push_heap(__first, __holeIndex, __topIndex, __value); }
priority queue
优先级队列实际上 stl_heap
中提供几种接口的一种封装。其模板有 3 个参数: priority_queue<_Tp, _Sequence, _Compare>
默认情况下:
_Sequence = vector _Compare = less
其提供的接口和 stack
比较类似:
push pop top
应用
- 堆排序
- 合并 K 个有序数组或者队列
- Dijstra 算法:单源最短路径
本文完
.
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。