注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

   

2013-05-24 12:57:47|  分类: 数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
目前知道的堆的应用即在O(logN)时间内找到数组A[N]中的最大值或最小值。
二叉堆简称堆,因为其他种类的堆如斐波那契堆,二项式堆等都很少用,所以一般讲堆即为二叉堆。二叉堆是这样定义的:形状为完全二叉树或近似,某结点的值比它的儿子值要么大要么小,且两子树均为堆。显而易见堆顶即为最大值或最小值。那么对于已经做好的堆直接取堆顶即可。那么关键在于怎么做堆。假设某一个结点左右子树已经为一个堆了,而该结点不符合堆的要求,这时应该把该结点下放,以最大堆为例,先把儿子中最大值与该结点互换,这样这个结点就肯定符合堆了。但是这样那个换了位置的子树可能不是堆了,若仍是堆则停止,不是堆则重复上面步骤。这样先从二叉树倒数第二层起构造一个个子堆,自下而上即可。
  评论这张
 
阅读(25)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018