本文正體字版由OpenCC轉換

[可並堆與左偏樹]

我們最常用的二叉堆，是最常用的優先隊列，它可以在O(logN)內實現插入和刪除最小值操作。但是對於合併兩個有序的優先隊列，二叉堆就顯得力不從心了。

左偏樹是一種可並堆(Mergeable Heap)，意思是可以在O(logN)時間內完成兩個堆的合併操作。左偏樹(Leftist Tree)，或者叫左傾樹，左式樹，左式堆(Leftist Heap)，左堆。顧名思義，它好象是向左偏的，實際上它是一種趨於非常不平衡的二叉樹結構，但卻能夠實現對數級的合併時間複雜度。

[左偏樹的定義]

左偏樹是一棵二叉樹，每個節點具有四個屬性：左子樹(left)，右子樹(right)，鍵值(key)，零路徑長(npl)。其中節點i的零路徑長的定義爲從i到i子樹中最近的沒有兩非空個子節點的節點的路徑的長度。空節點的零路徑長爲爲-1，只有一個非空子節點的節點的零路徑長爲0。左偏樹的節點之間除了滿足堆序以外，還應滿足節點左子節點的零路徑長不小於右子節點的零路徑長。

根據上述定義，很容易得出：對於非空節點i，滿足i.npl=i.right.npl+1。還有一個性質，一棵節點數爲N的左偏樹，根節點的零路徑長最大爲⎣log(N+1)⎦-1，即O(logN)，證明略。

[左偏樹的合併]

左偏樹的一切操作都是在合併的基礎上進行的，所以要先討論合併。

當合並兩個左偏樹節點a,b時，要求是這兩個節點是沒有包含關係的。假設a.key<b.key(如果不是這樣則交換a,b)，只需對a.right和b合併，合併後的結果作爲新的a.right。然後更新a.npl=a.right.npl+1。

可以證明，一次合併的時間複雜度爲O(log(A.size) + log(B.size))。

[左偏樹的插入和刪除]

對已有的左偏樹a插入新的值p，只需把p構建爲一個只有一個元素左偏樹節點b，然後合併a,b即可。

刪除左偏樹的最小節點，只需把根節點刪除，然後合併兩個子樹，作爲新的根節點。

[左偏樹的構建]

可以用一個隊列，使左偏樹的構建爲O(N)。具體方法爲

1. 把所有元素作爲一個單獨左偏樹節點放入隊列；
2. 不斷取出兩個隊首的左偏樹，合併這兩個左偏樹，然後放入隊尾；

[對左偏樹的比較]

左偏樹可以實現二叉堆的一切功能，而且還能實現二叉堆不易實現的合併，個人認爲實際編程中左偏樹更有理性，不容易錯。但左偏樹的算法時間常數要大於二叉堆，所以不能完全代替之。

和平衡樹相比，左偏樹採取了與平衡樹完全相反的構造策略。平衡樹爲了實現所有元素的快速查找，使節點儘量趨於平衡。而左偏樹的目的是實現快速的查詢最小值與合併操作，恰恰要讓節點儘量向左偏。最優的平衡樹，恰恰是最差的左偏樹，而最優的左偏樹，恰恰是平衡樹退化的結果。

斜堆、二項堆、斐波那契堆也是可並堆實現的有效方法，而且二項堆、斐波那契堆實際中會比左偏樹更快，但是在時間與編程複雜度的性價比上，左偏樹有着絕對的優勢。

BYVoid 原創講解，轉載請註明。

上次修改時間 2017-02-03