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