数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究软堆
软堆定义为简单堆数据结构的一种变体，它对五种操作具有恒定的均摊时间。这是通过仔细“破坏”（增加）堆中最多一定数量的值的键来实现的。恒定时间操作包括：
- create(s) − 创建一个新的软堆 s
- insert(s, y) − 将元素 y 插入到软堆 s 中
- meld(s, s′) − 将两个软堆 s 和 s′ 合并成一个，销毁两者
- delete(s, y) − 从软堆 s 中删除元素 y
- findmin(s) − 获取软堆 s 中键值最小的元素
- 其他堆，例如斐波那契堆，在没有任何破坏的情况下实现了这些界限中的大部分，但无法为关键的删除操作提供恒定时间界限。破坏量可以通过参数 ε 的选择来控制，但是设置的越低，插入所需的时间就越多（对于 ε 的错误率，为 O(log 1/ε)）。
- 更准确地说，软堆提供的保证如下：对于 0 和 1/2 之间的固定值 ε，在任何时间点，堆中最多会有 ε*m 个损坏的键，其中 m 是插入或损坏的元素数量 W。我们不能保证堆中*当前*的键只有固定百分比被损坏或增加：在不需要的插入和删除序列中，堆中的所有元素都可能具有增加或损坏的键。同样，不能保证从堆中使用findmin提取并删除的元素序列中，只有固定百分比具有损坏或增加的键：在不走运的情况下，只有损坏或增加的元素从堆中提取。
- 尽管软堆具有其局限性和不可预测性，但它们对于设计确定性算法非常有用。它们被用来获得迄今为止确定最小生成树的最佳复杂度。它们还可以用来构建最优的选择算法和近似排序算法，这些算法将每个元素设置在其最终位置附近，在这种情况下，插入排序速度很快。
更新于：2020年1月2日
353 次浏览
广告