ACM___________________________

2.1.2 可并堆的定義

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

H ← Merge(H₁,H₂)

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

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

2.2 左偏樹(shù)的定義

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

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

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

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

即key(i)≤key(parent(i))  這條性質(zhì)又叫堆性質(zhì)。符合該性質(zhì)的樹(shù)是堆有序的(Heap-Ordered)。有了性質(zhì)1，我們可以知道左偏樹(shù)的根節(jié)點(diǎn)是整棵樹(shù)的最小節(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ì)列的其它兩個(gè)基本操作（插入節(jié)點(diǎn)、刪除最小節(jié)點(diǎn)）進(jìn)行后維持堆性質(zhì)。在后面我們就會(huì)看到它的作用。

這兩條性質(zhì)是對(duì)每一個(gè)節(jié)點(diǎn)而言的，因此可以簡(jiǎn)單地從中得出，左偏樹(shù)的左右子樹(shù)都是左偏樹(shù)。

由這兩條性質(zhì)，我們可以得出左偏樹(shù)的定義：左偏樹(shù)是具有左偏性質(zhì)的堆有序二叉樹(shù)。

2.3 左偏樹(shù)的性質(zhì)

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

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

[性質(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。

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

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

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

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

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

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

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

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

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

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

三、左偏樹(shù)的操作

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

3.1 左偏樹(shù)的合并

C ← Merge(A,B)

Merge( ) 把A,B兩棵左偏樹(shù)合并，返回一棵新的左偏樹(shù)C，包含A和B中的所有元素。在本文中，一棵左偏樹(shù)用它的根節(jié)點(diǎn)的指針表示。

在合并操作中，最簡(jiǎn)單的情況是其中一棵樹(shù)為空（也就是，該樹(shù)根節(jié)點(diǎn)指針為NULL）。這時(shí)我們只須要返回另一棵樹(shù)。

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

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

合并了right(A) 和B之后，right(A) 的距離可能會(huì)變大，當(dāng)right(A) 的距離大于left(A) 的距離時(shí)，左偏樹(shù)的性質(zhì)2會(huì)被破壞。在這種情況下，我們只須要交換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)這樣合并后的樹(shù)C符合性質(zhì)1和性質(zhì)2，因此是一棵左偏樹(shù)。至此左偏樹(shù)的合并就完成了。

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

3.2 插入新節(jié)點(diǎn)

單節(jié)點(diǎn)的樹(shù)一定是左偏樹(shù)，因此向左偏樹(shù)插入一個(gè)節(jié)點(diǎn)可以看作是對(duì)兩棵左偏樹(shù)的合并。下面是插入新節(jié)點(diǎn)的代碼：

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

3.3 刪除最小節(jié)點(diǎn)

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

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

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

將n個(gè)節(jié)點(diǎn)構(gòu)建成一棵左偏樹(shù)，這也是一個(gè)常用的操作。

算法一 暴力算法——逐個(gè)節(jié)點(diǎn)插入，時(shí)間復(fù)雜度為O(nlogn)。

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

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

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

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

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

前 次和并的是兩棵只有1個(gè)節(jié)點(diǎn)的左偏樹(shù)。

接下來(lái)的 次合并的是兩棵有2個(gè)節(jié)點(diǎn)的左偏樹(shù)。

接下來(lái)的 次合并的是兩棵有4個(gè)節(jié)點(diǎn)的左偏樹(shù)。

……

接下來(lái)的 次合并的是兩棵有2^i-1個(gè)節(jié)點(diǎn)的左偏樹(shù)。

合并兩棵2ⁱ個(gè)節(jié)點(diǎn)的左偏樹(shù)時(shí)間復(fù)雜度為O(i)，因此算法二的總時(shí)間復(fù)雜度為： 。

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

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

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

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

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

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

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

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

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

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

刪除任意已知節(jié)點(diǎn)操作的代碼如下：

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

情況1：p的距離減小了。在這種情況下，由于q的距離只能縮小，當(dāng)循環(huán)結(jié)束時(shí)，要么根節(jié)點(diǎn)處理完了，q為空；要么p是q的右子樹(shù)并且dist(p)+1=dist(q)；如果dist(p)+1>dist(q)，那么p一定是q的左子樹(shù)，否則會(huì)出現(xiàn)q的右子樹(shù)距離縮小了，但是加1以后卻大于q的距離的情況，不符合左偏樹(shù)的性質(zhì)3。不論哪種情況，刪除操作都可以結(jié)束了。注意到，每一次循環(huán)，p的距離都會(huì)加1，而在循環(huán)體內(nèi)，dist(p)+1最終將成為某個(gè)節(jié)點(diǎn)的距離。根據(jù)性質(zhì)4，任何的距離都不會(huì)超過(guò)logn，所以循環(huán)體的執(zhí)行次數(shù)不會(huì)超過(guò)logn。

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

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

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

3.6 小結(jié)

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