\( \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. 求最大值 - max()
  2. 求最小值 - min()
  3. 刪除最大值 - pop_max()
  4. 刪除最小值 - pop_min()
  5. 元素入堆 - push()
詳細演算法可以參考原始論文
Min-Max Heaps and Generalized Priority Queues
如果不懂敘述就看code吧
以下提供模板:
張貼者： 於
標籤： ,

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)