如何在刪除min之後「堆積」基於數組的最小堆？

一旦調用remove min函數（這只是將索引1中的元素移除並將其替換爲數組中的最後一項），我將如何在java中「堆積」一個基於數組的最小堆。我很困惑，在刪除min發生之後，我會如何將數組放入最小堆中。如何在刪除min之後「堆積」基於數組的最小堆？

索引0始終在堆最小數組中保持爲空。父索引是i/2，右邊的孩子是2i + 1，左邊的孩子是2i。

任何幫助將不勝感激，謝謝你們！

來源

2014-10-31 Vimzy

取最後一個元素並將其複製到第一個位置。在第一個元素上減少堆積1並調用heapify()。堆應該修復自己。這具有O（log n）的複雜度

Min-Heapify-Down (Array A, int i): 
    left ← 2i 
    right ← 2i + 1 
    smallest ← i 

    if left ≤ heap_length[A] and A[left] < A[smallest] then: 
     smallest ← left 
    if right ≤ heap_length[A] and A[right] < A[smallest] then: 
     smallest ← right 

    if smallest ≠ i then: 
     swap A[i] ↔ A[smallest] 
     Min-Heapify-Down(A, smallest)

來源

2014-10-31 10:03:14 isklenar

雖然heapify代碼看起來像什麼？ – Vimzy 2014-10-31 10:05:45

與構建堆時使用的heapify（）相同。 – isklenar 2014-10-31 10:08:18

問題是，我在構建堆時使用的heapify使用父級作爲比較器，所以我會比較新的索引1元素，因爲它沒有父級。這就是讓我困惑的原因。 – Vimzy 2014-10-31 10:09:29

如何在刪除min之後「堆積」基於數組的最小堆？

回答

相關問題