日月卦長的模板庫
\( \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年5月3日 星期日
[ skew heap ] implementation 斜堆 實作
斜堆(Skew heap)也叫自適應堆(self-adjusting heap),它是(
重量
)
左偏樹
的一個變種。
相較於(
重量
)
左偏樹
,斜堆不需記錄其高度或是節點個數(size)等附加域,其合併(merge)的方式也較為簡潔,效率也較高。和(
重量
)
左偏樹
一樣,斜堆的push、pop的時間複雜度為\(\ord{log \; n}\)、查詢最值為\(\ord 1\)。
關於
複雜度分析
以下提供斜堆的實作,使用方法與STL priority_queue相似
沒有留言:
張貼留言
較新的文章
較舊的文章
首頁
訂閱:
張貼留言 (Atom)
沒有留言:
張貼留言