如何刪除（min-）堆中的最後一個節點？

Question

我正在學習考試，目前我在堆。我已經理解如何從一個堆中刪除一個節點，但是我可以找到一個我不能使用該算法刪除的情況。

問題是我想刪除15這是一個葉子和最小堆的最後一個節點。當您刪除堆中的節點時，您正在查找堆的最後一個節點，將其替換爲刪除節點，並檢查此節點的子節點是否大於此節點..然後以遞歸方式繼續此操作。

因此（15是最後一個元素，沒有孩子），我不知道如何刪除它。

 1 
    / \ 
    9  6 
/\ /
17 11 8 
/
15 

我認爲你可以刪除它，而無需執行其他任何操作。由於刪除節點=最後一個節點，所以基本上可以自行替換它。因此，它看起來像這樣：

 1 
    / \ 
    9  6 
/\ /
17 11 8 

我希望你能幫助我，我真的需要知道我的考試，我找不到任何有關在互聯網上這種情況下，任何東西。

Answer 1

刪除最後一個節點是非常簡單的任務 - 只是刪除它，沒有什麼可做的（除非遞減計數器並在需要時調整數組大小）。一般情況下，功能交換項目本身並不會改變（雖然無用的工作完成），但您可以檢查項目是否是最後一個，並省略交換。

請注意，刪除非頭元素是罕見的問題（您必須提供明確的訪問權限），大多數算法只使​​用最頂層的元素。

另請注意，您的圖片沒有顯示正確二進制堆，因爲堆是完整二叉樹，和所有級別（除最後一個）必須完全充滿，但你的樹有第三排的空位子。