2.1.2 可并堆的定義

可并堆(Mergeable Heap)也是一種抽象數(shù)據(jù)類型，它除了支持優(yōu)先隊(duì)列的三個基本操作(Insert, Minimum, Delete-Min)，還支持一個額外的操作——合并操作：

H ← Merge(H1,H2)

Merge( ) 構(gòu)造并返回一個包含H1和H2所有元素的新堆H。

O(n)，用它來實(shí)現(xiàn)可并堆，則合并操作必然成為算法的瓶頸。左偏樹(Leftist Tree)、二項(xiàng)堆(Binomial Heap) 和Fibonacci堆(Fibonacci Heap) 都是十分優(yōu)秀的可并堆。本文討論的是左偏樹，在后面我們將看到各種可并堆的比較。

2.2 左偏樹的定義

左偏樹(Leftist Tree)是一種可并堆的實(shí)現(xiàn)。左偏樹是一棵二叉樹，它的節(jié)點(diǎn)除了和二叉樹的節(jié)點(diǎn)一樣具有左右子樹指針( left, right )外，還有兩個屬性：鍵值和距離(dist)。鍵值上面已經(jīng)說過，是用于比較節(jié)點(diǎn)的大小。距離則是如下定義的：

節(jié)點(diǎn)i稱為外節(jié)點(diǎn)(external node)，當(dāng)且僅當(dāng)節(jié)點(diǎn)i的左子樹或右子樹為空 ( left(i) = NULL或right(i) = NULL )；節(jié)點(diǎn)i的距離(dist(i))是節(jié)點(diǎn)i到它的后代中，最近的外節(jié)點(diǎn)所經(jīng)過的邊數(shù)。特別的，如果節(jié)點(diǎn)i本身是外節(jié)點(diǎn)，則它的距離為0；而空節(jié)點(diǎn)的距離規(guī)定為-1 (dist(NULL) = -1)。在本文中，有時(shí)也提到一棵左偏樹的距離，這指的是該樹根節(jié)點(diǎn)的距離。

左偏樹滿足下面兩條基本性質(zhì)：

[性質(zhì)1] 節(jié)點(diǎn)的鍵值小于或等于它的左右子節(jié)點(diǎn)的鍵值。

即key(i)≤key(parent(i)) 這條性質(zhì)又叫堆性質(zhì)。符合該性質(zhì)的樹是堆有序的(Heap-Ordered)。有了性質(zhì)1，我們可以知道左偏樹的根節(jié)點(diǎn)是整棵樹的最小節(jié)點(diǎn)，于是我們可以在O(1) 的時(shí)間內(nèi)完成取最小節(jié)點(diǎn)操作。

[性質(zhì)2] 節(jié)點(diǎn)的左子節(jié)點(diǎn)的距離不小于右子節(jié)點(diǎn)的距離。

即dist(left(i))≥dist(right(i)) 這條性質(zhì)稱為左偏性質(zhì)。性質(zhì)2是為了使我們可以以更小的代價(jià)在優(yōu)先隊(duì)列的其它兩個基本操作（插入節(jié)點(diǎn)、刪除最小節(jié)點(diǎn)）進(jìn)行后維持堆性質(zhì)。在后面我們就會看到它的作用。
這兩條性質(zhì)是對每一個節(jié)點(diǎn)而言的，因此可以簡單地從中得出，左偏樹的左右子樹都是左偏樹。
由這兩條性質(zhì)，我們可以得出左偏樹的定義：左偏樹是具有左偏性質(zhì)的堆有序二叉樹。

2.3 左偏樹的性質(zhì)

在前面一節(jié)中，本文已經(jīng)介紹了左偏樹的兩個基本性質(zhì)，下面本文將介紹左偏樹的另外兩個性質(zhì)。

我們知道，一個節(jié)點(diǎn)必須經(jīng)由它的子節(jié)點(diǎn)才能到達(dá)外節(jié)點(diǎn)。由于性質(zhì)2，一個節(jié)點(diǎn)的距離實(shí)際上就是這個節(jié)點(diǎn)一直沿它的右邊到達(dá)一個外節(jié)點(diǎn)所經(jīng)過的邊數(shù)，也就是說，我們有

[性質(zhì)3] 節(jié)點(diǎn)的距離等于它的右子節(jié)點(diǎn)的距離加1。

即 dist( i ) = dist( right( i ) ) + 1 外節(jié)點(diǎn)的距離為0，由于性質(zhì)2，它的右子節(jié)點(diǎn)必為空節(jié)點(diǎn)。為了滿足性質(zhì)3，故前面規(guī)定空節(jié)點(diǎn)的距離為-1。

我們的印象中，平衡樹是具有非常小的深度的，這也意味著到達(dá)任何一個節(jié)點(diǎn)所經(jīng)過的邊數(shù)很少。左偏樹并不是為了快速訪問所有的節(jié)點(diǎn)而設(shè)計(jì)的，它的目的是快速訪問最小節(jié)點(diǎn)以及在對樹修改后快速的恢復(fù)堆性質(zhì)。從圖中我們可以看到它并不平衡，由于性質(zhì)2的緣故，它的結(jié)構(gòu)偏向左側(cè)，不過距離的概念和樹的深度并不同，左偏樹并不意味著左子樹的節(jié)點(diǎn)數(shù)或是深度一定大于右子樹。

下面我們來討論左偏樹的距離和節(jié)點(diǎn)數(shù)的關(guān)系。

[引理1] 若左偏樹的距離為一定值，則節(jié)點(diǎn)數(shù)最少的左偏樹是完全二叉樹。

證明：由性質(zhì)2可知，當(dāng)且僅當(dāng)對于一棵左偏樹中的每個節(jié)點(diǎn)i，都有 dist(left(i)) = dist(right(i)) 時(shí)，該左偏樹的節(jié)點(diǎn)數(shù)最少。顯然具有這樣性質(zhì)的二叉樹是完全二叉樹。

[定理1] 若一棵左偏樹的距離為k，則這棵左偏樹至少有2k+1-1個節(jié)點(diǎn)。

證明：由引理1可知，當(dāng)這樣的左偏樹節(jié)點(diǎn)數(shù)最少的時(shí)候，是一棵完全二叉樹。距離為k的完全二叉樹高度也為k，節(jié)點(diǎn)數(shù)為2k+1-1，所以距離為k的左偏樹至少有2k＋1-1個節(jié)點(diǎn)。

作為定理1的推論，我們有：

[性質(zhì)4] 一棵N個節(jié)點(diǎn)的左偏樹距離最多為log(N+1) -1。

證明：設(shè)一棵N個節(jié)點(diǎn)的左偏樹距離為k，由定理1可知，N ≥ 2k+1-1，因此k ≤ log(N+1) -1。

有了上面的4個性質(zhì)，我們可以開始討論左偏樹的操作了。

三、左偏樹的操作
本章將討論左偏樹的各種操作，包括插入新節(jié)點(diǎn)、刪除最小節(jié)點(diǎn)、合并左偏樹、構(gòu)建左偏樹和刪除任意節(jié)點(diǎn)。由于各種操作都離不開合并操作，因此我們先討論合并操作。

3.1 左偏樹的合并

C ← Merge(A,B)

Merge( ) 把A,B兩棵左偏樹合并，返回一棵新的左偏樹C，包含A和B中的所有元素。在本文中，一棵左偏樹用它的根節(jié)點(diǎn)的指針表示。
在合并操作中，最簡單的情況是其中一棵樹為空（也就是，該樹根節(jié)點(diǎn)指針為NULL）。這時(shí)我們只須要返回另一棵樹。

若A和B都非空，我們假設(shè)A的根節(jié)點(diǎn)小于等于B的根節(jié)點(diǎn)（否則交換A,B），把A的根節(jié)點(diǎn)作為新樹C的根節(jié)點(diǎn)，剩下的事就是合并A的右子樹right(A) 和B了。

right(A) ← Merge(right(A), B)

合并了right(A) 和B之后，right(A) 的距離可能會變大，當(dāng)right(A) 的距離大于left(A) 的距離時(shí)，左偏樹的性質(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

不難驗(yàn)證，經(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

下面我們來分析合并操作的時(shí)間復(fù)雜度。從上面的過程可以看出，每一次遞歸合并的開始，都需要分解其中一棵樹，總是把分解出的右子樹參加下一步的合并。根據(jù)性質(zhì)3，一棵樹的距離決定于其右子樹的距離，而右子樹的距離在每次分解中遞減，因此每棵樹A或B被分解的次數(shù)分別不會超過它們各自的距離。根據(jù)性質(zhì)4，分解的次數(shù)不會超過?log(N1+1)? + ?log(N2+1)? -2，其中N1和N2分別為左偏樹A和B的節(jié)點(diǎn)個數(shù)。因此合并操作最壞情況下的時(shí)間復(fù)雜度為O( ?log(N1+1)? + ?log(N2+1)? -2) = O(log N1 + log N2)。
3.2 插入新節(jié)點(diǎn)

單節(jié)點(diǎn)的樹一定是左偏樹，因此向左偏樹插入一個節(jié)點(diǎn)可以看作是對兩棵左偏樹的合并。下面是插入新節(jié)點(diǎn)的代碼：
Procedure Insert(x, A)

   B ← MakeIntoTree(x)

   A ← Merge(A, B)

End Procedure

由于合并的其中一棵樹只有一個節(jié)點(diǎn)，因此插入新節(jié)點(diǎn)操作的時(shí)間復(fù)雜度是O(logn)。

3.3 刪除最小節(jié)點(diǎn)
由性質(zhì)1，我們知道，左偏樹的根節(jié)點(diǎn)是最小節(jié)點(diǎn)。在刪除根節(jié)點(diǎn)后，剩下的兩棵子樹都是左偏樹，需要把他們合并。刪除最小節(jié)點(diǎn)操作的代碼也非常簡單：

Function DeleteMin(A)

   t ← key(root(A))

   A ← Merge(left(A), right(A))

   return t

End Function
由于刪除最小節(jié)點(diǎn)后只需進(jìn)行一次合并，因此刪除最小節(jié)點(diǎn)的時(shí)間復(fù)雜度也為O(logn)。

3.4 左偏樹的構(gòu)建

將n個節(jié)點(diǎn)構(gòu)建成一棵左偏樹，這也是一個常用的操作。
算法一 暴力算法——逐個節(jié)點(diǎn)插入，時(shí)間復(fù)雜度為O(nlogn)。

算法二 仿照二叉堆的構(gòu)建算法，我們可以得到下面這種算法：

? 將n個節(jié)點(diǎn)（每個節(jié)點(diǎn)作為一棵左偏樹）放入先進(jìn)先出隊(duì)列。

? 不斷地從隊(duì)首取出兩棵左偏樹，將它們合并之后加入隊(duì)尾。

? 當(dāng)隊(duì)列中只剩下一棵左偏樹時(shí)，算法結(jié)束。

下面分析算法二的時(shí)間復(fù)雜度。假設(shè)n=2k，則：

前 次和并的是兩棵只有1個節(jié)點(diǎn)的左偏樹。
接下來的 次合并的是兩棵有2個節(jié)點(diǎn)的左偏樹。
接下來的 次合并的是兩棵有4個節(jié)點(diǎn)的左偏樹。
…
接下來的 次合并的是兩棵有2i-1個節(jié)點(diǎn)的左偏樹。
合并兩棵2i個節(jié)點(diǎn)的左偏樹時(shí)間復(fù)雜度為O(i)，因此算法二的總時(shí)間復(fù)雜度為： 。

3.5 刪除任意已知節(jié)點(diǎn)

接下來是關(guān)于刪除任意已知節(jié)點(diǎn)的操作。之所以強(qiáng)調(diào)“已知”，是因?yàn)檫@里所說的任意節(jié)點(diǎn)并不是根據(jù)它的鍵值找出來的，左偏樹本身除了可以迅速找到最小節(jié)點(diǎn)外，不能有效的搜索指定鍵值的節(jié)點(diǎn)。故此，我們不能要求：請刪除所有鍵值為100的節(jié)點(diǎn)。

前面說過，優(yōu)先隊(duì)列是一種容器。對于通常的容器來說，一旦節(jié)點(diǎn)被放進(jìn)去以后，容器就完全擁有了這個節(jié)點(diǎn)，每個容器中的節(jié)點(diǎn)具有唯一的對象掌握它的擁有權(quán)（ownership）。對于這種容器的應(yīng)用，優(yōu)先隊(duì)列只能刪除最小節(jié)點(diǎn)，因?yàn)槟愀緹o從知道它的其它節(jié)點(diǎn)是什么。

但是優(yōu)先隊(duì)列除了作為一種容器外還有另一個作用，就是可以找到最小節(jié)點(diǎn)。很多應(yīng)用是針對這個功能的，它們并沒有將擁有權(quán)完全轉(zhuǎn)移給優(yōu)先隊(duì)列，而是把優(yōu)先隊(duì)列作為一個最小節(jié)點(diǎn)的選擇器，從一堆節(jié)點(diǎn)中依次將它們選出來。這樣一來節(jié)點(diǎn)的擁有權(quán)就可能同時(shí)被其它對象掌握。也就是說某個節(jié)點(diǎn)雖不是最小節(jié)點(diǎn)，不能從優(yōu)先隊(duì)列那里“已知”，但卻可以從其它的擁有者那里“已知”。

這種優(yōu)先隊(duì)列的應(yīng)用也是很常見的。設(shè)想我們有一個鬧鐘，它可以記錄很多個響鈴時(shí)間，不過由于時(shí)間是線性的，鈴只能一個個按先后次序響，優(yōu)先隊(duì)列就很適合用來作這樣的挑選。另一方面使用者應(yīng)該可以隨時(shí)取消一個“已知”的響鈴時(shí)間，這就需要進(jìn)行任意已知節(jié)點(diǎn)的刪除操作了。

我們的這種刪除操作需要指定被刪除的節(jié)點(diǎn)，這和原來的刪除根節(jié)點(diǎn)的操作是兼容的，因?yàn)楦?jié)點(diǎn)肯定是已知的。上面已經(jīng)提過，在刪除一個節(jié)點(diǎn)以后，將會剩下它的兩棵子樹，它們都是左偏樹，我們先把它們合并成一棵新的左偏樹。

p ← Merge(left(x), right(x))

現(xiàn)在p指向了這顆新的左偏樹，如果我們刪除的是根節(jié)點(diǎn)，此時(shí)任務(wù)已經(jīng)完成了。不過，如果被刪除節(jié)點(diǎn)x不是根節(jié)點(diǎn)就有點(diǎn)麻煩了。這時(shí)p指向的新樹的距離有可能比原來x的距離要大或小，這勢必有可能影響原來x的父節(jié)點(diǎn)q的距離，因?yàn)閝現(xiàn)在成為新樹p的父節(jié)點(diǎn)了。于是就要仿照合并操作里面的做法，對q的左右子樹作出調(diào)整，并更新q的距離。這一過程引起了連鎖反應(yīng)，我們要順著q的父節(jié)點(diǎn)鏈一直往上進(jìn)行調(diào)整。新樹p的距離為dist(p)，如果dist(p)+1等于q的原有距離dist(q)，那么不管p是q的左子樹還是右子樹，我們都不需要對q進(jìn)行任何調(diào)整，此時(shí)刪除操作也就完成了。

如果dist(p)+1小于q的原有距離dist(q)，那么q的距離必須調(diào)整為dist(p)+1，而且如果p是左子樹的話，說明q的左子樹距離比右子樹小，必須交換子樹。由于q的距離減少了，所以q的父節(jié)點(diǎn)也要做出同樣的處理。

剩下就是另外一種情況了，那就是p的距離增大了，使得dist(p)+1大于q的原有距離dist(q)。在這種情況下，如果p是左子樹，那么q的距離不會改變，此時(shí)刪除操作也可以結(jié)束了。如果p是右子樹，這時(shí)有兩種可能：一種是p的距離仍小于等于q的左子樹距離，這時(shí)我們直接調(diào)整q的距離就行了；另一種是p的距離大于q的左子樹距離，這時(shí)我們需要交換q的左右子樹并調(diào)整q的距離，交換完了以后q的右子樹是原來的左子樹，它的距離加1只能等于或大于q的原有距離，如果等于成立，刪除操作可以結(jié)束了，否則q的距離將增大，我們還要對q的父節(jié)點(diǎn)做出相同的處理。

刪除任意已知節(jié)點(diǎn)操作的代碼如下：
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

下面分兩種情況討論刪除操作的時(shí)間復(fù)雜度。

情況1：p的距離減小了。在這種情況下，由于q的距離只能縮小，當(dāng)循環(huán)結(jié)束時(shí)，要么根節(jié)點(diǎn)處理完了，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é)點(diǎn)的距離。根據(jù)性質(zhì)4，任何的距離都不會超過logn，所以循環(huán)體的執(zhí)行次數(shù)不會超過logn。

情況2：p的距離增大了。在這種情況下，我們將必然一直從右子樹向上調(diào)整，直至q為空或p是q的左子樹時(shí)停止。一直從右子樹升上來這個事實(shí)說明了循環(huán)的次數(shù)不會超過logn（性質(zhì)4）。

最后我們看到這樣一個事實(shí)，就是這兩種情況只會發(fā)生其中一個。如果某種情況的調(diào)整結(jié)束后，我們已經(jīng)知道要么q為空，要么dist(p)+1 = dist(q)，要么p是q的左子樹。這三種情況都不會導(dǎo)致另一情況發(fā)生。直觀上來講，如果合并后的新子樹導(dǎo)致了父節(jié)點(diǎn)的一系列距離調(diào)整的話，要么就一直是往小調(diào)整，要么是一直往大調(diào)整，不會出現(xiàn)交替的情況。

我們已經(jīng)知道合并出新子樹p的復(fù)雜度是O(logn)，向上調(diào)整距離的復(fù)雜度也是O(logn)，故刪除操作的最壞情況的時(shí)間復(fù)雜度是O(logn)。如果左偏樹非常傾斜，實(shí)際應(yīng)用情況下要比這個快得多。
3.6 小結(jié)

本章介紹了左偏樹的各種操作，我們可以看到，左偏樹作為可并堆的實(shí)現(xiàn)，它的各種操作性能都十分優(yōu)秀，且編程復(fù)雜度比較低，可以說是一個“性價(jià)比”十分高的數(shù)據(jù)結(jié)構(gòu)。左偏樹之所以是很好的可并堆實(shí)現(xiàn)，是因?yàn)樗軌虿蹲降骄哂卸研再|(zhì)的二叉樹里面的一些其它有用信息，沒有將這些信息浪費(fèi)掉。根據(jù)堆性質(zhì)，我們知道，從根節(jié)點(diǎn)向下到任何一個外節(jié)點(diǎn)的路徑都是有序的。存在越長的路徑，說明樹的整體有序性越強(qiáng)，與平衡樹不同（平衡樹根本不允許有很長的路徑），左偏樹盡大約一半的可能保留了這個長度，并將它甩向左側(cè)，利用它來縮短節(jié)點(diǎn)的距離以提高性能。這里我們不進(jìn)行嚴(yán)格的討論，左偏樹作為一個例子大致告訴我們：放棄已有的信息意味著算法性能上的犧牲。下面是最好的左偏樹：有序表（插入操作是按逆序發(fā)生的，自然的有序性被保留了）和最壞的左偏樹：平衡樹（插入操作是按正序發(fā)生的，自然的有序性完全被放棄了）。

左偏樹的一個實(shí)現(xiàn)方法：

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=10010;
struct Tree{
    int val,dis;
    Tree *lef,*rig;
}*root;
int distance(Tree *t)
{
    if(t==NULL) return -1;
    return t->dis;
}
Tree *merge(Tree *& A,Tree *& B)//最大堆
{
    if(A==NULL) return B;
    if(B==NULL) return A;
    if(B->val>A->val) swap(A,B);
    A->rig=merge(A->rig,B);
    if(distance(A->lef)<distance(A->rig)) swap(A->lef,A->rig);
    A->dis=distance(A->rig)+1;
    return A;
}
int deleteMax(Tree *&t)
{
    int value=t->val;
    Tree *tmp=t;
    t=merge(t->lef,t->rig);
    delete tmp;
    return value;
}
void init(Tree *&t,int value)
{
    t=new Tree();
    t->dis=0;
    t->lef=t->rig=NULL;
    t->val=value;
}
void insert(Tree *&t,int value)
{
    Tree *p;
    init(p,value);
    t=merge(t,p);
}
void deleteAll(Tree *&t)
{
    if(t==NULL) return;
    if(t->lef==NULL&&t->rig==NULL) delete t;
    deleteAll(t->lef);
    deleteAll(t->rig);
    delete t;
    t=NULL;
}
int main()
{
        root=NULL;
        for(int i=16;i<=30;i++)
       {
           insert(root,i);
       }
       deleteAll(root);
       for(int i=1;i<=15;i++)
       {
           insert(root,i);
       }
       for(int i=1;i<=15;i++)
       {
           cout<<deleteMax(root)<<endl;
       }
}