2.1.2 可并堆的定義
可并堆(Mergeable Heap)也是一種抽象數(shù)據(jù)類型，它除了支持優(yōu)先隊列的三個基本操作(Insert, Minimum, Delete-Min)，還支持一個額外的操作——合并操作：
H ← Merge(H1,H2)
Merge( ) 構(gòu)造并返回一個包含H1和H2所有元素的新堆H。
O(n)，用它來實現(xiàn)可并堆，則合并操作必然成為算法的瓶頸。左偏樹(Leftist Tree)、二項堆(Binomial Heap) 和Fibonacci堆(Fibonacci Heap) 都是十分優(yōu)秀的可并堆。本文討論的是左偏樹，在后面我們將看到各種可并堆的比較。
2.2 左偏樹的定義
左偏樹(Leftist Tree)是一種可并堆的實現(xiàn)。左偏樹是一棵二叉樹，它的節(jié)點除了和二叉樹的節(jié)點一樣具有左右子樹指針( left, right )外，還有兩個屬性：鍵值和距離(dist)。鍵值上面已經(jīng)說過，是用于比較節(jié)點的大小。距離則是如下定義的：
節(jié)點i稱為外節(jié)點(external node)，當且僅當節(jié)點i的左子樹或右子樹為空 ( left(i) = NULL或right(i) = NULL )；節(jié)點i的距離(dist(i))是節(jié)點i到它的后代中，最近的外節(jié)點所經(jīng)過的邊數(shù)。特別的，如果節(jié)點i本身是外節(jié)點，則它的距離為0；而空節(jié)點的距離規(guī)定為-1 (dist(NULL) = -1)。在本文中，有時也提到一棵左偏樹的距離，這指的是該樹根節(jié)點的距離。
左偏樹滿足下面兩條基本性質(zhì)：
[性質(zhì)1] 節(jié)點的鍵值小于或等于它的左右子節(jié)點的鍵值。
即key(i)≤key(parent(i)) 這條性質(zhì)又叫堆性質(zhì)。符合該性質(zhì)的樹是堆有序的(Heap-Ordered)。有了性質(zhì)1，我們可以知道左偏樹的根節(jié)點是整棵樹的最小節(jié)點，于是我們可以在O(1) 的時間內(nèi)完成取最小節(jié)點操作。
[性質(zhì)2] 節(jié)點的左子節(jié)點的距離不小于右子節(jié)點的距離。
即dist(left(i))≥dist(right(i)) 這條性質(zhì)稱為左偏性質(zhì)。性質(zhì)2是為了使我們可以以更小的代價在優(yōu)先隊列的其它兩個基本操作（插入節(jié)點、刪除最小節(jié)點）進行后維持堆性質(zhì)。在后面我們就會看到它的作用。
這兩條性質(zhì)是對每一個節(jié)點而言的，因此可以簡單地從中得出，左偏樹的左右子樹都是左偏樹。
由這兩條性質(zhì)，我們可以得出左偏樹的定義：左偏樹是具有左偏性質(zhì)的堆有序二叉樹。
2.3 左偏樹的性質(zhì)
在前面一節(jié)中，本文已經(jīng)介紹了左偏樹的兩個基本性質(zhì)，下面本文將介紹左偏樹的另外兩個性質(zhì)。
我們知道，一個節(jié)點必須經(jīng)由它的子節(jié)點才能到達外節(jié)點。由于性質(zhì)2，一個節(jié)點的距離實際上就是這個節(jié)點一直沿它的右邊到達一個外節(jié)點所經(jīng)過的邊數(shù)，也就是說，我們有
[性質(zhì)3] 節(jié)點的距離等于它的右子節(jié)點的距離加1。
即 dist( i ) = dist( right( i ) ) + 1 外節(jié)點的距離為0，由于性質(zhì)2，它的右子節(jié)點必為空節(jié)點。為了滿足性質(zhì)3，故前面規(guī)定空節(jié)點的距離為-1。
我們的印象中，平衡樹是具有非常小的深度的，這也意味著到達任何一個節(jié)點所經(jīng)過的邊數(shù)很少。左偏樹并不是為了快速訪問所有的節(jié)點而設(shè)計的，它的目的是快速訪問最小節(jié)點以及在對樹修改后快速的恢復(fù)堆性質(zhì)。從圖中我們可以看到它并不平衡，由于性質(zhì)2的緣故，它的結(jié)構(gòu)偏向左側(cè)，不過距離的概念和樹的深度并不同，左偏樹并不意味著左子樹的節(jié)點數(shù)或是深度一定大于右子樹。
下面我們來討論左偏樹的距離和節(jié)點數(shù)的關(guān)系。
[引理1] 若左偏樹的距離為一定值，則節(jié)點數(shù)最少的左偏樹是完全二叉樹。
證明：由性質(zhì)2可知，當且僅當對于一棵左偏樹中的每個節(jié)點i，都有 dist(left(i)) = dist(right(i)) 時，該左偏樹的節(jié)點數(shù)最少。顯然具有這樣性質(zhì)的二叉樹是完全二叉樹。
[定理1] 若一棵左偏樹的距離為k，則這棵左偏樹至少有2k+1-1個節(jié)點。
證明：由引理1可知，當這樣的左偏樹節(jié)點數(shù)最少的時候，是一棵完全二叉樹。距離為k的完全二叉樹高度也為k，節(jié)點數(shù)為2k+1-1，所以距離為k的左偏樹至少有2k＋1-1個節(jié)點。
作為定理1的推論，我們有：
[性質(zhì)4] 一棵N個節(jié)點的左偏樹距離最多為ëlog(N+1)û -1。
證明：設(shè)一棵N個節(jié)點的左偏樹距離為k，由定理1可知，N ≥ 2k+1-1，因此k ≤ ëlog(N+1)û -1。
有了上面的4個性質(zhì)，我們可以開始討論左偏樹的操作了。
三、左偏樹的操作
本章將討論左偏樹的各種操作，包括插入新節(jié)點、刪除最小節(jié)點、合并左偏樹、構(gòu)建左偏樹和刪除任意節(jié)點。由于各種操作都離不開合并操作，因此我們先討論合并操作。
3.1 左偏樹的合并
C ← Merge(A,B)
Merge( ) 把A,B兩棵左偏樹合并，返回一棵新的左偏樹C，包含A和B中的所有元素。在本文中，一棵左偏樹用它的根節(jié)點的指針表示。
在合并操作中，最簡單的情況是其中一棵樹為空（也就是，該樹根節(jié)點指針為NULL）。這時我們只須要返回另一棵樹。
若A和B都非空，我們假設(shè)A的根節(jié)點小于等于B的根節(jié)點（否則交換A,B），把A的根節(jié)點作為新樹C的根節(jié)點，剩下的事就是合并A的右子樹right(A) 和B了。
right(A) ← Merge(right(A), B)
合并了right(A) 和B之后，right(A) 的距離可能會變大，當right(A) 的距離大于left(A) 的距離時，左偏樹的性質(zhì)2會被破壞。在這種情況下，我們只須要交換left(A) 和right(A)。
若dist(left(A)) > dist(right(A))，交換left(A) 和right(A)
最后，由于right(A) 的距離可能發(fā)生改變，我們必須更新A的距離：
dist(A) ← dist(right(A)) + 1
不難驗證，經(jīng)這樣合并后的樹C符合性質(zhì)1和性質(zhì)2，因此是一棵左偏樹。至此左偏樹的合并就完成了。
我們可以用下面的代碼描述左偏樹的合并過程：
Function Merge(A, B) If A = NULL Then return B If B = NULL Then return A If key(B) < key(A) Then swap(A, B) right(A) ← Merge(right(A), B) If dist(right(A)) > dist(left(A)) Then swap(left(A), right(A)) If right(A) = NULL Then dist(A) ← 0 Else dist(A) ← dist(right(A)) + 1 return A End Function |
下面我們來分析合并操作的時間復(fù)雜度。從上面的過程可以看出，每一次遞歸合并的開始，都需要分解其中一棵樹，總是把分解出的右子樹參加下一步的合并。根據(jù)性質(zhì)3，一棵樹的距離決定于其右子樹的距離，而右子樹的距離在每次分解中遞減，因此每棵樹A或B被分解的次數(shù)分別不會超過它們各自的距離。根據(jù)性質(zhì)4，分解的次數(shù)不會超過ëlog(N1+1)û + ëlog(N2+1)û -2，其中N1和N2分別為左偏樹A和B的節(jié)點個數(shù)。因此合并操作最壞情況下的時間復(fù)雜度為O( ëlog(N1+1)û + ëlog(N2+1)û -2) = O(log N1 + log N2)。
3.2 插入新節(jié)點
單節(jié)點的樹一定是左偏樹，因此向左偏樹插入一個節(jié)點可以看作是對兩棵左偏樹的合并。下面是插入新節(jié)點的代碼：
Procedure Insert(x, A) B ← MakeIntoTree(x) A ← Merge(A, B) End Procedure |
由于合并的其中一棵樹只有一個節(jié)點，因此插入新節(jié)點操作的時間復(fù)雜度是O(logn)。
3.3 刪除最小節(jié)點
由性質(zhì)1，我們知道，左偏樹的根節(jié)點是最小節(jié)點。在刪除根節(jié)點后，剩下的兩棵子樹都是左偏樹，需要把他們合并。刪除最小節(jié)點操作的代碼也非常簡單：
Function DeleteMin(A) t ← key(root(A)) A ← Merge(left(A), right(A)) return t End Function |
由于刪除最小節(jié)點后只需進行一次合并，因此刪除最小節(jié)點的時間復(fù)雜度也為O(logn)。
3.4 左偏樹的構(gòu)建
將n個節(jié)點構(gòu)建成一棵左偏樹，這也是一個常用的操作。
算法一 暴力算法——逐個節(jié)點插入，時間復(fù)雜度為O(nlogn)。
算法二 仿照二叉堆的構(gòu)建算法，我們可以得到下面這種算法：
Ø 將n個節(jié)點（每個節(jié)點作為一棵左偏樹）放入先進先出隊列。
Ø 不斷地從隊首取出兩棵左偏樹，將它們合并之后加入隊尾。
Ø 當隊列中只剩下一棵左偏樹時，算法結(jié)束。
下面分析算法二的時間復(fù)雜度。假設(shè)n=2k，則：
前 次和并的是兩棵只有1個節(jié)點的左偏樹。
接下來的 次合并的是兩棵有2個節(jié)點的左偏樹。
接下來的 次合并的是兩棵有4個節(jié)點的左偏樹。
……
接下來的 次合并的是兩棵有2i-1個節(jié)點的左偏樹。
合并兩棵2i個節(jié)點的左偏樹時間復(fù)雜度為O(i)，因此算法二的總時間復(fù)雜度為： 。
3.5 刪除任意已知節(jié)點
接下來是關(guān)于刪除任意已知節(jié)點的操作。之所以強調(diào)“已知”，是因為這里所說的任意節(jié)點并不是根據(jù)它的鍵值找出來的，左偏樹本身除了可以迅速找到最小節(jié)點外，不能有效的搜索指定鍵值的節(jié)點。故此，我們不能要求：請刪除所有鍵值為100的節(jié)點。
前面說過，優(yōu)先隊列是一種容器。對于通常的容器來說，一旦節(jié)點被放進去以后，容器就完全擁有了這個節(jié)點，每個容器中的節(jié)點具有唯一的對象掌握它的擁有權(quán)（ownership）。對于這種容器的應(yīng)用，優(yōu)先隊列只能刪除最小節(jié)點，因為你根本無從知道它的其它節(jié)點是什么。
但是優(yōu)先隊列除了作為一種容器外還有另一個作用，就是可以找到最小節(jié)點。很多應(yīng)用是針對這個功能的，它們并沒有將擁有權(quán)完全轉(zhuǎn)移給優(yōu)先隊列，而是把優(yōu)先隊列作為一個最小節(jié)點的選擇器，從一堆節(jié)點中依次將它們選出來。這樣一來節(jié)點的擁有權(quán)就可能同時被其它對象掌握。也就是說某個節(jié)點雖不是最小節(jié)點，不能從優(yōu)先隊列那里“已知”，但卻可以從其它的擁有者那里“已知”。
這種優(yōu)先隊列的應(yīng)用也是很常見的。設(shè)想我們有一個鬧鐘，它可以記錄很多個響鈴時間，不過由于時間是線性的，鈴只能一個個按先后次序響，優(yōu)先隊列就很適合用來作這樣的挑選。另一方面使用者應(yīng)該可以隨時取消一個“已知”的響鈴時間，這就需要進行任意已知節(jié)點的刪除操作了。
我們的這種刪除操作需要指定被刪除的節(jié)點，這和原來的刪除根節(jié)點的操作是兼容的，因為根節(jié)點肯定是已知的。上面已經(jīng)提過，在刪除一個節(jié)點以后，將會剩下它的兩棵子樹，它們都是左偏樹，我們先把它們合并成一棵新的左偏樹。
p ← Merge(left(x), right(x))
現(xiàn)在p指向了這顆新的左偏樹，如果我們刪除的是根節(jié)點，此時任務(wù)已經(jīng)完成了。不過，如果被刪除節(jié)點x不是根節(jié)點就有點麻煩了。這時p指向的新樹的距離有可能比原來x的距離要大或小，這勢必有可能影響原來x的父節(jié)點q的距離，因為q現(xiàn)在成為新樹p的父節(jié)點了。于是就要仿照合并操作里面的做法，對q的左右子樹作出調(diào)整，并更新q的距離。這一過程引起了連鎖反應(yīng)，我們要順著q的父節(jié)點鏈一直往上進行調(diào)整。新樹p的距離為dist(p)，如果dist(p)+1等于q的原有距離dist(q)，那么不管p是q的左子樹還是右子樹，我們都不需要對q進行任何調(diào)整，此時刪除操作也就完成了。
如果dist(p)+1小于q的原有距離dist(q)，那么q的距離必須調(diào)整為dist(p)+1，而且如果p是左子樹的話，說明q的左子樹距離比右子樹小，必須交換子樹。由于q的距離減少了，所以q的父節(jié)點也要做出同樣的處理。
剩下就是另外一種情況了，那就是p的距離增大了，使得dist(p)+1大于q的原有距離dist(q)。在這種情況下，如果p是左子樹，那么q的距離不會改變，此時刪除操作也可以結(jié)束了。如果p是右子樹，這時有兩種可能：一種是p的距離仍小于等于q的左子樹距離，這時我們直接調(diào)整q的距離就行了；另一種是p的距離大于q的左子樹距離，這時我們需要交換q的左右子樹并調(diào)整q的距離，交換完了以后q的右子樹是原來的左子樹，它的距離加1只能等于或大于q的原有距離，如果等于成立，刪除操作可以結(jié)束了，否則q的距離將增大，我們還要對q的父節(jié)點做出相同的處理。
刪除任意已知節(jié)點操作的代碼如下：
Procedure Delete(x) q ← parent(x) p ← Merge(left(x), right(x)) parent(p) ← q If q ≠ NULL and left(q) = x Then left(q) ← p If q ≠ NULL and right(q) = x Then right(q) ← p While q ≠ NULL Do If dist(left(q)) < dist(right(q)) Then swap(left(q), right(q)) If dist(right(q))+1 = dist(q) Then Exit Procedure dist(q) ← dist(right(q))+1 p ← q q ← parent(q) End While End Procedure |
下面分兩種情況討論刪除操作的時間復(fù)雜度。
情況1：p的距離減小了。在這種情況下，由于q的距離只能縮小，當循環(huán)結(jié)束時，要么根節(jié)點處理完了，q為空；要么p是q的右子樹并且dist(p)+1=dist(q)；如果dist(p)+1>dist(q)，那么p一定是q的左子樹，否則會出現(xiàn)q的右子樹距離縮小了，但是加1以后卻大于q的距離的情況，不符合左偏樹的性質(zhì)3。不論哪種情況，刪除操作都可以結(jié)束了。注意到，每一次循環(huán)，p的距離都會加1，而在循環(huán)體內(nèi)，dist(p)+1最終將成為某個節(jié)點的距離。根據(jù)性質(zhì)4，任何的距離都不會超過logn，所以循環(huán)體的執(zhí)行次數(shù)不會超過logn。
情況2：p的距離增大了。在這種情況下，我們將必然一直從右子樹向上調(diào)整，直至q為空或p是q的左子樹時停止。一直從右子樹升上來這個事實說明了循環(huán)的次數(shù)不會超過logn（性質(zhì)4）。
最后我們看到這樣一個事實，就是這兩種情況只會發(fā)生其中一個。如果某種情況的調(diào)整結(jié)束后，我們已經(jīng)知道要么q為空，要么dist(p)+1 = dist(q)，要么p是q的左子樹。這三種情況都不會導(dǎo)致另一情況發(fā)生。直觀上來講，如果合并后的新子樹導(dǎo)致了父節(jié)點的一系列距離調(diào)整的話，要么就一直是往小調(diào)整，要么是一直往大調(diào)整，不會出現(xiàn)交替的情況。
我們已經(jīng)知道合并出新子樹p的復(fù)雜度是O(logn)，向上調(diào)整距離的復(fù)雜度也是O(logn)，故刪除操作的最壞情況的時間復(fù)雜度是O(logn)。如果左偏樹非常傾斜，實際應(yīng)用情況下要比這個快得多。
3.6 小結(jié)
本章介紹了左偏樹的各種操作，我們可以看到，左偏樹作為可并堆的實現(xiàn)，它的各種操作性能都十分優(yōu)秀，且編程復(fù)雜度比較低，可以說是一個“性價比”十分高的數(shù)據(jù)結(jié)構(gòu)。左偏樹之所以是很好的可并堆實現(xiàn)，是因為它能夠捕捉到具有堆性質(zhì)的二叉樹里面的一些其它有用信息，沒有將這些信息浪費掉。根據(jù)堆性質(zhì)，我們知道，從根節(jié)點向下到任何一個外節(jié)點的路徑都是有序的。存在越長的路徑，說明樹的整體有序性越強，與平衡樹不同（平衡樹根本不允許有很長的路徑），左偏樹盡大約一半的可能保留了這個長度，并將它甩向左側(cè)，利用它來縮短節(jié)點的距離以提高性能。這里我們不進行嚴格的討論，左偏樹作為一個例子大致告訴我們：放棄已有的信息意味著算法性能上的犧牲。下面是最好的左偏樹：有序表（插入操作是按逆序發(fā)生的，自然的有序性被保留了）和最壞的左偏樹：平衡樹（插入操作是按正序發(fā)生的，自然的有序性完全被放棄了）。