資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告