前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布

d-堆

作者头像
233333
发布2019-09-25 12:19:01
4290
发布2019-09-25 12:19:01
举报
文章被收录于专栏:linux驱动个人学习

二叉堆因为实现简单,因此在需要优先队列的时候几乎总是使用二叉堆。d-堆是二叉堆的简单推广,它恰像一个二叉堆,只是所有的节点都有d个儿子(因此,二叉堆又叫2-堆)。下图表示的是一个3-堆。注意,d-堆要比二叉堆浅得多,它将Insert操作的运行时间改进为。然而,对于大的d,DeleteMin操作费时得多,因为虽然树浅了,但是d个儿子中的最小者是必须找到的,如果使用标准算法,将使用d-1次比较,于是将此操作的时间提高到 。如果d是常数,那么当然两种操作的运行时间都为 O(logN)。虽然仍可以使用一个数组,但是,现在找出儿子和父亲的乘法和除法都有个因子d,除非d是2的幂,否则会大大增加运行时间,因为我们不能再通过二进制移位来实现除法和乘法了。D-堆在理论上很有趣,因为存在许多算法,其插入次数比删除次数多得多,而且,当优先队列太大不能完全装入内存的时候,d-堆也是很有用的,在这种情况下,d-堆能够以与B-树大致相同的方式发挥作用。

除了不能执行Find操作外(指以对数执行),堆的实现最明显的两个缺点是:将两个堆合并成一个堆是很困难的。这种附加的操作叫做Merge。存在许多实现堆的方法使得Merge操作的运行时间为O(logN),如下篇介绍的左式堆。

image
image
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019-09-14 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档