資料結構和演算法教學 » 堆

堆

堆是平衡二元樹資料結構，其中根節點鍵與它的子相比並設定相應在一種特殊情況。如果α有子節點β那麼 -

key(α) ≥ key(β)

作為父的值大於這個子，這個屬性會產生最大堆。基於該標準堆可以有兩種型別 - 

For Input → 35 33 42 10 14 19 27 44 26 31

  • 最小堆 ? 其中根節點的值小於或等於任一其子點。

Max Heap Example

  • 最大堆 ? 其中根節點的值大於或等於任一其子節點。

Max Heap Example

兩個樹都使用相同的輸入及到達順序構成。

最大堆構造演算法

我們將用同樣的例子來說明如何建立最大堆。程式建立最大堆與最小堆是類似，但使用最小值代替最大值。

我們將通過一次插入一個元素以匯出最大堆演算法。在任何時間點，堆必須保持其效能。 當在插入時，假設插入在堆欄位在樹中的節點。 

Step 1 ? 在堆的末尾建立新節點
Step 2 ? 分配節點的新值
Step 3 ? 比較其父與這個孩子節點的值
Step 4 ? 如果父值小於子，那麼交換它們
Step 5 ? 重複步驟3和4，直到堆屬性儲存

註 ? 在最小堆構造演算法，預計父節點的值要小於子節點。

我們先看一張卡通插圖來了解最大堆構建。拿我們之前用的相同輸入樣本。

Max Heap Animated Example

最大堆刪除演算法

讓我們推導一個演算法的最大堆刪除。刪除最大（小）堆總是發生在根部去除最大（或最小）值。 

Step 1 ? 刪除
Step 2 ? 分配節點的新值
Step 3 ? 比較其父與這個孩子節點的值
Step 4 ? 如果父值小於子，那麼交換它們
Step 5 ? 重複步驟3和4，直到堆屬性儲存
Max Heap Deletion Animated Example