可併堆(I) ── 左偏樹 Leftist Tree
讓我們回憶一下一般的優先佇列可以做到的事情：
- Insert(): 插入一個元素到佇列 裡頭。
- Find-Min(): 從佇列 裡頭取出最小元素。
- Delete-Min(): 從佇列 裡頭移除最小元素。
如果今天我們希望的是能夠有效率地合併兩個優先佇列 ，那麼使用單純的 Heap 來實作可能就不是那麼明智的選擇了。在最壞情形下使用 Heap 實作合併可能會耗費 的線性時間。
左偏樹是一種特化的樹狀資料結構，它最大的賣點就是在 Worst Case 的觀點下能夠進行有效率地合併兩個優先佇列。簡而言之，左偏樹實作了支援以下操作的資料型別：
- Insert(): 插入一個元素到 。
- Find-Min(): 從佇列 裡頭取出最小元素。
- Delete-Min(): 從佇列 裡頭移除最小元素。
- Merge(): 合併兩個優先佇列 以及 。
通常支援 Merge 操作的優先佇列我們統稱為可併堆資料結構（Mergeable Heaps）
1 左偏樹的特性
對於每一個節點 ，我們定義一個秩函數 為從該節點一路往右子樹走到葉子的距離。那麼，左偏樹滿足以下不變量：
不變亮，就變暗
- 它是一棵二元樹，每一個非葉節點都有左子樹和右子樹（子樹可能為空）
- 樹中每個元素小於（或大於）其父親節點的值（堆的性質）
- 令 和 分別表示 的左右子節點，則
由上面的不變量，我們可以推論出以下的重要引理
引理（左偏樹的秩函數上界）
令 為有 個節點的左偏樹的根節點，則
這個引理可以透過數學歸納法輕鬆證明：令樹根的 值為 。 當 的時候，顯然整棵樹至少有 個點。 當 的時候，由定義可知左子樹與右子樹的秩函數至少為 。根據歸納假設，我們知道左子樹與右子樹的點數至少有 個。因此整棵樹至少有 個點。得證。
值得注意的是：我們僅能得到每個節點一路往右邊走的長度上界。對於左邊的子樹來說，長度是沒有明確地上限的（因此這也是為什麼發明者 Clark A. Crane 稱呼這棵樹是「左偏」的緣故）。這給了我們一些關於合併兩棵樹的線索：永遠往右子樹合併去。
2 左偏樹的 Merge
Find-Min() 就是找 的 root 的元素，不過 Insert、Delete-Min 和 Merge 用以前一般優先佇列的操作是無法全部完成的。但是我們發現，如果能夠實現 Merge 的操作，那麼 Insert 和 Delete-Min 這兩個操作就能夠輕易地實現了，合併的演算法如下:
Merge():
Step 1. 挑出 、 之 root 元素的最小值作為新樹之 root（不妨假設 的樹根比較小）。
Step 2. 之 root 為新樹之 root，且 之左子樹保留，透過遞迴呼叫將 之右子樹與 合併。
Step 3. 檢查 的左右子樹是否滿足不變量3.的性質，若沒有，就交換左右子樹。
遞迴裡頭也是重複前三個步驟，直到合併完成（至少一個子樹為空）。
Insert() 可以用 Merge() 來實現；Delete-Min() 則可以在刪除 的根節點後，將 的左右子樹 Merge 起來完成。
複雜度分析
每次合併時，因為沿著兩個要結合的左偏樹最右邊的路徑向下移動，根據引理.，可以知道路徑長度最多為對數等級、而每一層的操作為常數等級。假設兩棵樹的大小分別為 和 ，那麼 Merge 的複雜度為 。
由此可知 Insert 和 Delete-Min 的複雜度也為 。
3 實作左偏樹
請參考日月卦長的模板庫──左偏樹：http://sunmoon-template.blogspot.com/2014/12/leftist-tree.html
4 實戰應用
APIO 2012 - Dispatching (忍者調度問題)
- 題目連結
- 中文題目連結
- BZOJ 2809: http://www.lydsy.com/JudgeOnline/problem.php?id=2809
- 題解連結
- 參考資料（解題討論）：http://codeforces.com/blog/entry/8875