最大—最小堆

最大堆和最小堆是二叉堆的兩種形式。

最大堆：根結點的鍵值是所有堆結點鍵值中最大者的堆。最小堆：根結點的鍵值是所有堆結點鍵值中最小者的堆。

而最大-最小堆集結了最大堆和最小堆的優點，這也是其名字的由來。 最大-最小堆是最大層和最小層交替出現的二叉樹，即最大層結點的兒子屬於最小層，最小層結點的兒子屬於最大層。 以最大（小）層結n點為根結點的子樹保有最大（小）堆性質：根結點的鍵值為該子樹結點鍵值中最大（小）項。

基本介紹

• 中文名：最大—最小堆
• 外文名：Min-max heap
• 學科：計算機科學

主要操作

不失一般性，只討論根結點為最小層的情況。

插入

只需要將節點插在二叉樹的最後一個葉子結點位置，然後比較它對它父親節點的大小，如果大則停止；如果小則交換位置，然後對父親節點遞歸該過程直至根節點。複雜度為。

一般來說，插入的位置可以不是最後一個葉子節點，可以作為任意中間節點的孩子節點插入，將這個葉子節點變為中間節點後，按上文所說的方法調整節點順序以保證維持堆特性不變。

刪除

要從堆中刪除一個節點，用最後一個節點替換掉要刪除的節點，然後調整節點順序以維持堆特性。

套用

雙端優先佇列。