软堆定义为简单堆数据结构的一种变体,它由5种类型的操作的固定摊销时间组成。这是通过仔细“破坏”(增加)堆中最大数量的值的键来实现的。恒定时间操作是-
create(s) -创建一个新的软堆
insert(s,y) -将元素y插入软堆s
将两个软堆s和s'融合成一个,同时破坏两者
delete(s,y) -从软堆s中删除元素y
findmin(s) -在软堆s中获得具有最小键的元素
其他堆(例如Fibonacci堆)可以在没有任何损坏的情况下实现大多数限制,但不能在关键删除操作上提供恒定时间限制。可以通过选择参数ε来控制损坏的程度,但是将其设置得越低,所需的插入时间就越长(错误率ε为O(log 1 /ε))。
更准确地说,软堆提供的保证如下:对于介于0和1/2之间的固定值ε,在任何时间点,堆中最多有ε* m个损坏的键,其中m是W插入或损坏的元素。我们不能保证堆中当前只有固定百分比的键被破坏或增加:在不必要的插入和删除序列中,可能发生堆中的所有元素都会增加或删除。键损坏。在同一情况下,不能保证在使用findmin和delete从堆中提取的元素序列中,只有固定百分比的键会损坏或增加:在不幸的情况下,只会从堆中提取损坏或增加的元素。
尽管有其局限性和不可预测的性质,但软堆对于确定性算法的设计很有用。实施它们是为了获得迄今为止确定最小生成树的最佳复杂性。它们也可以实现为简单地构建最佳选择算法和近分类算法,近分类算法是将每个元素都设置在其最终位置附近的算法,在这种情况下 插入分类很快。