\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2015年12月21日 星期一

[ min-max heap ] 最小-最大堆

最小-最大堆(Min-Max Heaps)是一個完整二元樹。此二元樹是交替的階層方式呈現,分別為最小階層 ( min level ) 和最大階層 ( max level ) ,這裡實作樹根為最大鍵值。

這裡最小-最大堆的建立規則為:
階度1的鍵值 > 階度3的鍵值 > 階度5的鍵值…> 階度n的鍵值(n為奇數)
階度2的鍵值 < 階度4的鍵值 < 階度6的鍵值…< 階度n的鍵值(n為偶數)

最小-最大堆是一種堆積支援以下幾種操作:
  1. 求最大值 - max()
  2. 求最小值 - min()
  3. 刪除最大值 - pop_max()
  4. 刪除最小值 - pop_min()
  5. 元素入堆 - push()
求最大最小的做法很容易理解,這裡就不再多講了。
現在先來講入堆(以最大階層為例):
  1. 因為它是一顆完滿二元樹,所以直接將入堆的元素加在最尾端即可
  2. 因為要滿足最小-最大堆的建立規則,所以如果他的值比他父母小就把他跟他父母的值交換
  3. 之後一直跟祖父母節點的值做比較,如果他的值比祖父母節點的值還大就把他跟祖父母節點交換(類似於維護一般的最大堆,只是不跟父母比較),值到祖父母不存在
再來是講刪除節點(以最大階層為例):
  1. 因為它是一顆完滿二元樹,所以把尾端元素換到要刪除元素的位置再將尾端刪除(現在要刪除元素的位置的值是尾端元素)
  2. 如果要刪除元素有孫節點(下下層),就把他跟最大的孫節點交換
  3. 如果要刪除元素沒有孫節點但有子節點,就把他跟最大的子節點交換
  4. 如果比較後最大的節點比要刪除元素小,就不交換
  5. 如果沒有子節點就結束程式
如果不懂敘述就看code吧
以下提供模板:

沒有留言:

張貼留言