最小最大堆中的刪除最大值操作

我正在實現最小最大值堆，這是一種雙端優先級隊列。你可以看這裏here關於最小最大堆的更多信息。最小最大堆中的刪除最大值操作

插入和刪除分鐘操作的代碼很簡單，可以在網上獲得。但是，我也試圖在最小 - 最大堆上執行delete-max操作。最初，我覺得min-max堆中的delete-max與max-min堆中的delete-max相同（如果我們考慮包含最大元素的min-max堆的子樹，它類似於max-分鐘堆）。因此，實現將很簡單，類似於min-max堆的delete-min。

但是，有一個問題： enter image description here

如在上面的圖中可以看出，雖然圖70是最大元件，最後元件（12）的最大 - 最小堆的不包含70的子樹。那麼，我可以用它來代替刪除70後留在左側子樹中的空位嗎？

如果我們不使用該元素，而是遵循最大最小堆的刪除-MAX程序，並使用20來代替差距，插在堆中的下一個元素將是在10和永遠正確的孩子將沒有右邊的孩子9.

那麼，任何人都可以幫助我嗎？

來源

2013-01-15 avinash

由於關於刪除隨機密鑰的問題與如何在delete-max之後修復堆的問題不同，因此我會考慮將其作爲一個單獨的問題。 – templatetypedef

@templatetypedef編輯此問題以關注「如何刪除最大元素」。現在，您可以在此處找到一個關於「如何從最小 - 最大堆中刪除任何節點」的建議解決方案的具體問題：http://stackoverflow.com/q/39392864/3924118 – nbro

我相信刪除最後一層最右邊的節點並使用它來替換被刪除的最大元素是正確的，即使它在樹中交叉。的理由如下：

刪除最右邊的節點在最後一個級別不會改變任何需要保持在樹中的任何節點不變的：所有的分層次的節點仍小於他們的所有後代，以及所有最高級別的節點都比他們的後代更大。
該樹仍然是一個完整的二叉樹。

一旦搬到這個節點上，您就可以使用正常的修正過程中的最大最小堆，以確保左子樹不變量仍持有。

希望這會有所幫助！

來源

2013-01-15 06:47:01 templatetypedef

這也是我實現它的方式，當時我幾個月前寫了一個min-max-heap數據結構。（+1） –

這可以刪除最小 - 最大堆中的_maximum_元素，但是您確定這適用於最小 - 最大堆中的任何節點嗎？如果是的話，你會準確使用哪個「fixup」？使用「滴入」操作不起作用，請檢查我對此問題所做的唯一評論，其中顯示問題：https：//gist.github.com/gnarmis/4647645 – nbro

最小最大堆中的刪除最大值操作

回答

相關問題