\( \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"}} \)

2014年12月27日 星期六

左偏樹 leftist tree

一個左偏樹同時滿足了heap及左偏的性質
設:
deep(x)為x到任意一個外部節點的最長路徑長度
滿足: deep(x)={0,x為外部節點 : 1+max(deep(x->leftchild),deep(x->rightchild))}
由於左偏堆已經不是完全二元樹,因此不能用數組存儲表示,需要用連結結構。
插入刪除最差複雜度\(\ord{log \; n}\)最佳\(\ord 1\)
插入時盡量往右邊插入,若不符合左偏性質則交換左右子樹
刪除則是將根節點的左右子樹合併,再直接刪除根節點
以下是模板:

(感謝"脹脹的承翰"幫忙指正)
定義一個int為key的左偏樹:

//標準是大根堆
leftist_tree<int  > t;

//小根堆的左偏樹
leftist_tree<int ,greater<int > >t;

基本上與priority_queue的用法差不多,只是多了clear()及join()指令
t.clear();//將t清空
t.join(b);//將b加入t,並將b清空

1 則留言: