雙優先順序佇列

存在從單端優先順序佇列(PQ)資料結構匯出高效DEPQ(雙端優先順序佇列)資料結構的通用方法，這些方法也提供了高效的remove(bNode)操作的實現(此操作從PQ中刪除節點bNode)。最簡單的這種方法，雙結構方法，同時維護一個最小PQ和一個最大PQ，其中包含DEPQ的所有元素，並在最小PQ和最大PQ的節點之間設定對應指標，這些節點包含相同的元素。

圖D顯示了元素7、8、3、6、5的雙堆結構。對應指標顯示為紅色箭頭。

圖D：雙堆

儘管圖中顯示每個元素都儲存在最小堆和最大堆中，但實際上只需要將每個元素儲存在兩個堆中的一個即可。

isEmpty和size操作透過實現一個變數size來實現，該變數跟蹤DEPQ中元素的數量。最小元素位於最小堆的根部，最大元素位於最大堆的根部。要插入元素B，我們將B插入最小堆和最大堆，然後在B在最小堆和最大堆中的位置之間設定對應指標。要消除最小元素，我們從最小堆中執行removeMin，並從最大堆中執行remove(bNode)，其中bNode是已刪除元素的對應節點。最大元素的消除方式類似。

Arnab Chakraborty

更新於：2020年1月3日

226 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始