软堆是一种数据结构，能够完成堆所支持的所有操作。

在计算机科学中, 被Bernard Chazelle在2000年发明的软堆, 是基本堆结构的变体。 通过小心地”变质“ (增加) 堆中不超过某个特定比例的关键字, 就能够使得堆的5个操作均达到均摊的常数时间复杂度

以下是软堆所支持的操作：

create(S): 新建一个软堆。

insert(S, x): 向软堆中插入一个元素

meld(S, S' ): 合并两个软堆

delete(S, x): 从软堆中删除一个元素

findmin(S): 从软堆中得到最小的一个元素

下面解释一下”变质“的含义。软堆中的每个节点都包含一系列的关键字列表和一个普通关键字。这普通关键字是关键字列表中的所有值的上界。一旦一个关键字被加入到关键字列表中，就被认为是变质了，因为在软堆的所有操作中，只会比较普通关键字的大小，而关键字列表都是无关的。哪个关键字会按照这种方法变质是无法预测的，我们只知道最多到一个特定比例的关键字都会变质。这就是所谓的”软“堆。你不能知道哪个放入的关键字会变质。这种变质过程成功地降低了数据的信息熵，这样就能让数据结构的时间复杂度打破信息论所给出的界限。

另外的堆结构如菲波纳契堆也能通过不变质数据达到大多数操作的常数时间复杂度，但是不能在关键的删除操作中达到常数级别的时间复杂度。变质的比例上限可以任意选择，不过这个比例越低，插入所需要的时间就越高。（在ε的错误率下，时间复杂度为O(log 1/ε)）

应用

令人惊讶的是，软堆在确定性算法中很有效，尽管这个数据结构包含着不确定性。在迄今为止发现的最好的最小生成树算法中软堆成为了关键。软堆还可以用来简单地构造一个最优的选择算法，或者接近排序算法（这是一个把所有关键字排序到接近其应有位置的算法，这样继续使用插入排序时间效率就会很高）

一个很简单的例子就是选择算法。比如说，我们想找到n个数当中的第k大数。第一次，我们选择1/3的错误率，也就是说最多1/3的数据会变质。现在，我们把n个数全部插入软堆，这时，最多n/3的数据是变质的。然后，我们大约n/3次删除堆中的最小元素。因为这样只是在删除元素，所以不可能增加堆中变质的元素数量，所以现在仍然最多有n/3个元素是变质的。

现在，至少2n/3 − n/3 = n/3个剩下的元素是不是变质的，而且都比我们已经删除掉的元素大。设L为我们删除掉的最大元素（我们指的是变质之前的值，这个值存在一系列关键字列表当中，因此这个元素不一定是最后一个删除的元素）L比其他我们删除的n/3个元素都要大，但比剩下的n/3个没变质的元素要小。所以，L把原来的数列划分成两部分，这两部分的比例在33%/66%到66%/33%之间。然后，我们用快速排序中的分划算法把原数列划分成比L小和比L大的两部分。这两部分都不比2n/3大。因为每次插入删除都需要均摊的O(1)时间复杂度，所以最终的时间复杂度是T(n)=T(2n/3)+O(n)。使用主定理的第三种情况我们就知道T(n)=Θ(n)

最后给出程序的伪代码：

function softHeapSelect(a[1..n], k)

if k = 1 then return minimum(a[1..n])

create(S)

for i from 1 to n

insert(S, a[i])

for i from 1 to n/3

x := findmin(S)

delete(S, x)

xIndex := partition(a, x) // Returns new index of pivot x

if k < xIndex

softHeapSelect(a[1..xIndex-1], k)

else

softHeapSelect(a[xIndex..n], k-xIndex+1)