ACM___________________________

2.1.2 可并堆的定義

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

H ← Merge(H₁,H₂)

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

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

2.2 左偏樹的定義

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

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

左偏樹滿足下面兩條基本性質：

[性質1] 節點的鍵值小于或等于它的左右子節點的鍵值。

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

[性質2] 節點的左子節點的距離不小于右子節點的距離。

即dist(left(i))≥dist(right(i)) 這條性質稱為左偏性質。性質2是為了使我們可以以更小的代價在優先隊列的其它兩個基本操作（插入節點、刪除最小節點）進行后維持堆性質。在后面我們就會看到它的作用。

這兩條性質是對每一個節點而言的，因此可以簡單地從中得出，左偏樹的左右子樹都是左偏樹。

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

2.3 左偏樹的性質

在前面一節中，本文已經介紹了左偏樹的兩個基本性質，下面本文將介紹左偏樹的另外兩個性質。

我們知道，一個節點必須經由它的子節點才能到達外節點。由于性質2，一個節點的距離實際上就是這個節點一直沿它的右邊到達一個外節點所經過的邊數，也就是說，我們有

[性質3] 節點的距離等于它的右子節點的距離加1。

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

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

下面我們來討論左偏樹的距離和節點數的關系。

[引理1] 若左偏樹的距離為一定值，則節點數最少的左偏樹是完全二叉樹。

證明：由性質2可知，當且僅當對于一棵左偏樹中的每個節點i，都有 dist(left(i)) = dist(right(i)) 時，該左偏樹的節點數最少。顯然具有這樣性質的二叉樹是完全二叉樹。

[定理1] 若一棵左偏樹的距離為k，則這棵左偏樹至少有2^k+1-1個節點。

證明：由引理1可知，當這樣的左偏樹節點數最少的時候，是一棵完全二叉樹。距離為k的完全二叉樹高度也為k，節點數為2^k+1-1，所以距離為k的左偏樹至少有2^k＋1-1個節點。

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

[性質4] 一棵N個節點的左偏樹距離最多為ëlog(N+1)û -1。

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

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

三、左偏樹的操作

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

3.1 左偏樹的合并

C ← Merge(A,B)

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

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

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

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

合并了right(A) 和B之后，right(A) 的距離可能會變大，當right(A) 的距離大于left(A) 的距離時，左偏樹的性質2會被破壞。在這種情況下，我們只須要交換left(A) 和right(A)。

若dist(left(A)) > dist(right(A))，交換left(A) 和right(A)

最后，由于right(A) 的距離可能發生改變，我們必須更新A的距離：

dist(A) ← dist(right(A)) + 1

不難驗證，經這樣合并后的樹C符合性質1和性質2，因此是一棵左偏樹。至此左偏樹的合并就完成了。

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

3.2 插入新節點

單節點的樹一定是左偏樹，因此向左偏樹插入一個節點可以看作是對兩棵左偏樹的合并。下面是插入新節點的代碼：

由于合并的其中一棵樹只有一個節點，因此插入新節點操作的時間復雜度是O(logn)。

3.3 刪除最小節點

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

由于刪除最小節點后只需進行一次合并，因此刪除最小節點的時間復雜度也為O(logn)。

3.4 左偏樹的構建

將n個節點構建成一棵左偏樹，這也是一個常用的操作。

算法一 暴力算法——逐個節點插入，時間復雜度為O(nlogn)。

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

Ø        將n個節點（每個節點作為一棵左偏樹）放入先進先出隊列。

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

Ø        當隊列中只剩下一棵左偏樹時，算法結束。

下面分析算法二的時間復雜度。假設n=2^k，則：

前 次和并的是兩棵只有1個節點的左偏樹。

接下來的 次合并的是兩棵有2個節點的左偏樹。

接下來的 次合并的是兩棵有4個節點的左偏樹。

……

接下來的 次合并的是兩棵有2^i-1個節點的左偏樹。

合并兩棵2ⁱ個節點的左偏樹時間復雜度為O(i)，因此算法二的總時間復雜度為： 。

3.5 刪除任意已知節點

接下來是關于刪除任意已知節點的操作。之所以強調“已知”，是因為這里所說的任意節點并不是根據它的鍵值找出來的，左偏樹本身除了可以迅速找到最小節點外，不能有效的搜索指定鍵值的節點。故此，我們不能要求：請刪除所有鍵值為100的節點。

前面說過，優先隊列是一種容器。對于通常的容器來說，一旦節點被放進去以后，容器就完全擁有了這個節點，每個容器中的節點具有唯一的對象掌握它的擁有權（ownership）。對于這種容器的應用，優先隊列只能刪除最小節點，因為你根本無從知道它的其它節點是什么。

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

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

我們的這種刪除操作需要指定被刪除的節點，這和原來的刪除根節點的操作是兼容的，因為根節點肯定是已知的。上面已經提過，在刪除一個節點以后，將會剩下它的兩棵子樹，它們都是左偏樹，我們先把它們合并成一棵新的左偏樹。

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

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

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

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

刪除任意已知節點操作的代碼如下：

下面分兩種情況討論刪除操作的時間復雜度。

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

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

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

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

3.6 小結

本章介紹了左偏樹的各種操作，我們可以看到，左偏樹作為可并堆的實現，它的各種操作性能都十分優秀，且編程復雜度比較低，可以說是一個“性價比”十分高的數據結構。左偏樹之所以是很好的可并堆實現，是因為它能夠捕捉到具有堆性質的二叉樹里面的一些其它有用信息，沒有將這些信息浪費掉。根據堆性質，我們知道，從根節點向下到任何一個外節點的路徑都是有序的。存在越長的路徑，說明樹的整體有序性越強，與平衡樹不同（平衡樹根本不允許有很長的路徑），左偏樹盡大約一半的可能保留了這個長度，并將它甩向左側，利用它來縮短節點的距離以提高性能。這里我們不進行嚴格的討論，左偏樹作為一個例子大致告訴我們：放棄已有的信息意味著算法性能上的犧牲。下面是最好的左偏樹：有序表（插入操作是按逆序發生的，自然的有序性被保留了）和最壞的左偏樹：平衡樹（插入操作是按正序發生的，自然的有序性完全被放棄了）。