博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
数据结构 d-堆
阅读量:5875 次
发布时间:2019-06-19

本文共 583 字,大约阅读时间需要 1 分钟。

d-堆

因为实现简单,因此在需要优先队列的时候几乎总是使用二叉堆。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),如下篇介绍的左式堆。

 

二叉堆

转载于:https://www.cnblogs.com/anzhi/p/7536426.html

你可能感兴趣的文章
让函式库更容易移植 JetBrains推出Kotlin 1.3
查看>>
Duality对偶性
查看>>
jQuery剥皮二 - extend
查看>>
异地恋怎么维持?
查看>>
RHEL下 ssh,telnet,ftp限制源IP访问
查看>>
C#数据导出Excel详细介绍
查看>>
Saltstack实战配置client_acl
查看>>
asp中的<script runat=server>和<% %>的区别
查看>>
Eova用户答疑-念小山
查看>>
redis安装---linux
查看>>
nginx中区分开发环境和生产环境
查看>>
mysql 用户管理和权限设置
查看>>
RouterOS实战:pppoe上网、web服务、远程管理
查看>>
实战Gradle——第二部分 掌握基础知识
查看>>
个别重要的网站链接(更新中)
查看>>
Tomcat源码解读系列——Tomcat的核心组成和启动过程
查看>>
mysql8默认时区不正确
查看>>
我的友情链接
查看>>
CSS:IE,Chrome,Firefox兼容性和CSS Hack
查看>>
fdisk
查看>>