[ Minimum Spanning Tree, kruskal, prim ] 最小生成樹經典演算法

以前覺得這應該是很簡單的東西，但我發現網路上使用priority_queue的prim演算法相關程式碼我覺得寫不好，我就把我自己的放上來。這裡順便也放上kruskal的程式碼。

prim $\ord{\left(\abs{V}+\abs{E}\right)\log{\abs{V}}}$:
kruskal $\ord{\abs{V}+\abs{E}\log{\abs{E}}}$:

[ 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吧
以下提供模板:

[ skew heap ] implementation 斜堆 實作

斜堆(Skew heap)也叫自適應堆(self-adjusting heap)，它是(重量)左偏樹的一個變種。
相較於(重量)左偏樹，斜堆不需記錄其高度或是節點個數(size)等附加域，其合併(merge)的方式也較為簡潔，效率也較高。和(重量)左偏樹一樣，斜堆的push、pop的時間複雜度為\(\ord{log \; n}\)、查詢最值為\(\ord 1\)。
關於複雜度分析
以下提供斜堆的實作，使用方法與STL priority_queue相似

重量左偏樹 weight-biased leftist tree

之前提到的左偏樹是深度左偏樹，雖然複雜度也是logn，但是重量左偏樹的速度在實作上是明顯較深度左偏樹快的
若是想了解深度左偏樹 height-biased leftist tree 或是左偏樹的理論請參考這篇文章
以下提供模板(使用方法與深度左偏樹相同):

左偏樹 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清空