首页 > 编程语言 > 详细

算法导论 二项堆

时间:2017-04-24 10:50:34      阅读:197      评论:0      收藏:0      [点我收藏+]

可以合并的堆 二项堆

先看看堆得操作运行时间的对比 对于使用这种数据结构有个概念

技术分享

二项堆在union操作合并上有优势

二项堆由二项树组成 我们先看看二项树的定义

技术分享

因为性质3中的系数就是二项式分布的系数,所以二项树名由此得来

B0 有2º = 1个节点

技术分享

B? 有2¹=2个节点 且根节点比子节点小

技术分享

B? 有2²=4个节点 且根节点比子节点小

技术分享

B? 有2³=8个节点 且根节点比子节点小

技术分享

二项堆则按照以下规则有二项树组成

技术分享

技术分享

由图 因为二项堆都是最小堆有序的,最小节点必定在跟节点中,寻找最小关键字就比较简单了 直接从head[H]中遍历查找就好了 图中经过查找 10 1 6 得到最小关键字 1

 

算法导论 二项堆

原文:http://www.cnblogs.com/itdef/p/6755489.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!