STL priority queue and heap

栏目: 编程工具 · 发布时间: 6年前

内容简介:对于支持假定已经是一个

简介

heap

对于支持 RandomAccessIterator 的容器适用。默认构造最大堆。

  • push_heap
    • 元素放在末尾,然后 __push_heap
  • pop_heap
    • pop 元素会放在末尾,然后插入末尾的元素
  • make_heap
    • [0, n/2) 不断地去 __adjust_heap
  • 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 算法:单源最短路径

本文完

STL priority queue and heap

This work is licensed under a CC A-S 4.0 International License

.


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

媒介融合

媒介融合

[丹]延森 / 刘君 / 复旦大学出版社 / 2012-9 / 32.00元

“媒介融合”是什么,如何来认识,本书提供的视角令人赞叹。 作为丹麦知名教授,延森具有欧陆学者的气质:思辨、批判。在延森看来,媒介融合带来了研究上的转向——从作为技术的媒介转向作为实践的传播,后者的一个中心命题是 特定的媒介与传播实践将对社会组织(从微观到宏观)产生何种影响? 解决上述问题,首先需要解决交流与传播观念的理论规范问题,本书就是阶段性的成果:基于对交流/传播观念史的考察,建构......一起来看看 《媒介融合》 这本书的介绍吧!

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试