-
最大—最小堆
鎖定
最大堆和最小堆是二叉堆的兩種形式。
- 中文名
- 最大—最小堆
- 外文名
- Min-max heap
- 學 科
- 計算機科學
最大—最小堆主要操作
最大—最小堆插入
只需要將節點插在二叉樹的最後一個葉子結點位置,然後比較它對它父親節點的大小,如果大則停止;如果小則交換位置,然後對父親節點遞歸該過程直至根節點。複雜度為
。
一般來説,插入的位置可以不是最後一個葉子節點,可以作為任意中間節點的孩子節點插入,將這個葉子節點變為中間節點後,按上文所説的方法調整節點順序以保證維持堆特性不變。
最大—最小堆刪除
要從堆中刪除一個節點,用最後一個節點替換掉要刪除的節點,然後調整節點順序以維持堆特性。
最大—最小堆應用
雙端優先隊列。
最大堆:根結點的鍵值是所有堆結點鍵值中最大者的堆。最小堆:根結點的鍵值是所有堆結點鍵值中最小者的堆。
而最大-最小堆集結了最大堆和最小堆的優點,這也是其名字的由來。 最大-最小堆是最大層和最小層交替出現的二叉樹,即最大層結點的兒子屬於最小層,最小層結點的兒子屬於最大層。 以最大(小)層結n點為根結點的子樹保有最大(小)堆性質:根結點的鍵值為該子樹結點鍵值中最大(小)項。