軟堆是一種數據結構，能夠完成堆所支持的所有操作。
基本介紹
- 中文名：軟堆
- 類型：完成堆所支持的所有操作
簡介,套用,代碼,
簡介
在計算機科學中, 被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)
