從區間堆中移除最小元素

  • 在區間堆中，最小元素位於根節點的左側。該元素被移除並返回。
  • 為了填補根節點左側建立的空缺，從最後一個節點移除一個元素，並再次插入到根節點。
  • 然後，將此元素依次與所有下降節點的左側元素進行比較，當滿足區間堆的所有條件時，該過程終止。
  • 如果在任何階段節點中的左側元素變得高於右側元素，則交換這兩個元素，然後執行進一步的比較。
  • 最後，根節點將再次包含左側的最小元素。

此過程也可以用以下方式解釋 -

最小元素的移除可以透過多種方式處理 -

  • 當區間堆為空時，removeMin 操作失敗。
  • 當區間堆只有一個元素時，應返回此元素。我們留下一個沒有任何元素的區間堆。
  • 當存在多個元素時，應返回根的左端點。此點從根中移除。
  • 如果根指示區間堆的最後一個節點，則無需執行更多操作。
  • 當最後一個節點不是根節點時，我們從最後一個節點移除左端點 p。如果這導致最後一個節點變為空，則最後一個節點不再是堆的一部分。
  • 從最後一個節點移除的點 p 透過從根開始重新插入到嵌入的最小堆中。
  • 當我們向下移動時，可能需要將當前 p 與正在檢查的節點的右端點 r 交換，以確保 p ≤r。重新插入是透過實現與重新插入普通堆相同的策略來執行的。

更新於: 2020年1月2日

308 次檢視

開啟您的 職業生涯

透過完成課程獲得認證

開始學習
廣告