STL中heap算法(堆算法)

STL中heap算法(堆算法)



①push_heap算法
以下是push_heap算法的实现细节。该函数接收两个迭代器,用来表现一个heap底部容器(vector)的头尾,而且新元素已经插入究竟部的最尾端。
template <class RandomAccessIterator>
inline void push_heap(RandomAccessIterator first,RandomAccessIterator last)
{
 //注意,此函数被调用时,新元素应已置于底部容器的最尾端
 _push_heap_aux(first,last,distance_type(first),value_type(first)); 
}

template <class RandomAccessIterator,class Distance,class T>
inline void _push_heap_aux(RandomAccessIterator first,RandomAccessIterator last,
Distance*,T*)
{
 //以上系依据heap的结构特性:新值必置于底部容器的最尾端,此即第一个洞号:(last-first)-1
 _push_heap(first,Distance((last-first)-1),Distance(0),T(*(last-1)));
}

template <class RandomAccessIterator,class Distance,class T>
void _push_heap(RandomAccessIterator first,Distance holeIndex,Distance topIndex,T value)
{
 Distance parent = (holeIndex-1)/2;
 while (parent > topIndex && *(first+parent)<value)
 {
  *(first + holeIndex) = *(first + parent);
  holeIndex = parent;
  parent = (holeIndex-1)/2;
 }
 *(first + holeIndex) = value;
}

②pop_heap算法
pop操作取走根节点(事实上是设至底部容器vector的尾端节点)后,为了满足complete binary tree的条件,必须割舍最下层最右边的叶节点,并将其值又一次安插至最大堆。
template <class RandomAccessIterator>
inline void pop_heap(RandomAccessIterator first,RandomAccessIterator last)
{
 _pop_heap_aux(first,last,value_type(first));
}

template <class RandomAccessIterator,class T>
inline void _pop_heap_aux(RandomAccessIterator first,RandomAccessIterator last,T*)
{
 _pop_heap(first,last-1,last-1,T(*(last-1)),distance_type(first));
}

template <class RandomAccessIterator,class T,class Distance>
inline void _pop_heap(RandomAccessIterator first,RandomAccessIterator last,RandomAccessIterator result,
T value,Distance*)
{
 *result = *first;
 _adjust_heap(first,Distance(0),Distance(last-first),value);
 //以上欲又一次调整heap,洞号为0(亦即树根处),欲调整值为value(原尾值)
}

template <class RandomAccessIterator,class Distance,class T>
void _adjust_heap(RandomAccessIterator first,Distance holeIndex,Distance len,T value)
{
 Distance topIndex = holeIndex;
 Distance secondChild = holeIndex*2+2;
 while (secondChild < len)
 {
  if(*(first+secondChild) < *(first+secondChild-1))
   secondChild–;
  *(first+holeIndex) = *(first+secondChild);
  holeIndex = secondChild;
  secondChild = holeIndex*2+2;
 }
 if (secondChild == len)
 {
  *(first+holeIndex) = *(first+secondChild-1);
  holeIndex = secondChild-1;
 }
 _push_heap(first,holeIndex,topIndex,value);
}

注意:pop_heap之后,最大元素仅仅是被置于底部容器的最尾端,尚未被取走。假设要取其值,可使用底部容器(vector)所提供的back()操作函数。假设要移除它,可使用底部容器(vector)所提供的pop_back()操作函数。
③sort_heap算法
既然每次pop_heap可获得heap中键值最大的元素,假设持续对整个heap做pop_heap操作,每次将操作范围从后向前缩减一个元素(由于pop_heap会把键值最大的元素放在底部容器的最尾端),当整个程序运行完成时,我们便有了一个递增序列。
template<class RandomAccessIterator>
void sort_heap(RandomAccessIterator first,RandomAccessIterator last)
{
 while(last – first > 1)
  pop_heap(first,last–);
}

④make_heap算法
这个算法用来将一段现有的数据转化为一个heap。
template <class RandomAccessIterator>
inline void make_heap(RandomAccessIterator first,RandomAccessIterator last)
{
 _make_heap(first,last,value_type(first),distance_type(first));
}

template <class RandomAccessIterator,class T,class Distance>
void _make_heap(RandomAccessIterator first,RandomAccessIterator last,T*,Distance*)
{
 if (last – first < 2) return;
 Distance len  = last-first;
 Distance parent = (len-1)/2;

 while (true)
 {
  _adjust_heap(first,parent,len,T(*(first+parent)));
  if (parent == 0)
   return;
  parent–;
 }
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/119095.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • js解压gzip_unzip解压命令

    js解压gzip_unzip解压命令//js解压gzipfunctionunzip(key){//解压//将二进制字符串转换为字符数组varcharData=key.split(”).map(function(x){returnx.charCodeAt(0);});//将数字数组转换成字节数组varbinData=newUint…

  • 如何关闭vscode git工具[通俗易懂]

    如何关闭VScode工具的git提示只需要关闭用户设置里的Git:Enabled即可;第一步,我们只需要打开”文件->首选项->设置”第二步,在搜索栏中搜索git:Enabled,关闭即可;…

  • Bad Request (Invalid Hostname)什么意思? 200

    Bad Request (Invalid Hostname)什么意思? 200

  • uml结构建模_uml面向对象分析建模与设计

    uml结构建模_uml面向对象分析建模与设计文章目录一、UML建模与架构文档化1、UML应用与未来2、UML基础a.用例和用例图b.交互图c.类图与对象图3、基 于 UML 的软件开发过程4、系统架构文档化二、设计模式类之间的关系及原则一、类之间的关系(我拿Visio作图举例)1.继承关系2、实现关系3、依赖关系4、关联关系5、聚合关系6、组合关系二、设计模式的原则(简单列出)三、设计模式1.创建型模式2、结构型模式3、行为型模式下面简单做…

  • 在线快速将pdf转换成word[通俗易懂]

    在线快速将pdf转换成word[通俗易懂]在线快速将pdf转换成word处理同样1000个PDF文件的格式转换,在线PDF转换成Word转换器比普通PDF转换器快8-12倍以上,是一款全自动化的转换模式,为用户提供了高质量的PDF转换服务的同时,大大节省了转换过程中所消耗的时间。今天小编给你支招的这款pdf转换成word转换器在线是专业转换网站,能够给你多种格式转换的选择。  相对于电脑版PDF转换器而言,近期

  • python的常见矩阵除法_Python矩阵除法

    python的常见矩阵除法_Python矩阵除法我有一个关于按元素划分矩阵的问题,我的意思是我想要第一个矩阵的元素[I,j]除以第二个矩阵(Q)的元素[I,j]。在一些背景信息:我从我的存储器加载了一个图像。我把每个像素的单色值存储在一个叫做“pixelMatrix”的矩阵中此命令将大矩阵(128×128)转换为较小的矩阵(8×8)foto_dct=skimage.util.view_as_blocks(pixelMatrix,block…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号