左偏樹的特點(diǎn)及其應(yīng)用

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

t—key(root(A))A—Merge(left(A),right(A))returntEndFunction由于刪除最小節(jié)點(diǎn)后只需進(jìn)行一次合并，因此刪除最小節(jié)點(diǎn)的時(shí)間復(fù)雜度也為O(logn)。3.4左偏樹的構(gòu)建將n個(gè)節(jié)點(diǎn)構(gòu)建成一棵左偏樹，這也是一個(gè)常用的操作。算法一暴力算法逐個(gè)節(jié)點(diǎn)插入，時(shí)間復(fù)雜度為O(nlogn)。算法二仿照二叉堆的構(gòu)建算法，我們可以得到下面這種算法：將n個(gè)節(jié)點(diǎn)(每個(gè)節(jié)點(diǎn)作為一棵左偏樹)放入先進(jìn)先出隊(duì)列。不斷地從隊(duì)首取出兩棵左偏樹，將它們合并之后加入隊(duì)尾。>當(dāng)隊(duì)列中只剩下一棵左偏樹時(shí)，算法結(jié)束。123456

構(gòu)建流程F面分析算法二的時(shí)間復(fù)雜度。假設(shè)n=2k，則:前n次和并的是兩棵只有1個(gè)節(jié)點(diǎn)的左偏樹。2接下來(lái)的n次合并的是兩棵有2個(gè)節(jié)點(diǎn)的左偏樹。4接下來(lái)的8次合并的是兩棵有4個(gè)節(jié)點(diǎn)的左偏樹。接下來(lái)的守次合并的是兩棵有2i-1個(gè)節(jié)點(diǎn)的左偏樹。合并兩棵2i個(gè)節(jié)點(diǎn)的左偏樹時(shí)間復(fù)雜度為0(i),因此算法二的總時(shí)間復(fù)雜nnn^-kik+2度為：—*O(1)+*O(2)+*O(3)+...=O(n*￡)=O(n*(2-))=O(n)。2482i2ki=13.5刪除任意已知節(jié)點(diǎn)接下來(lái)是關(guān)于刪除任意已知節(jié)點(diǎn)的操作。之所以強(qiáng)調(diào)“已知”是因?yàn)檫@里所說(shuō)的任意節(jié)點(diǎn)并不是根據(jù)它的鍵值找出來(lái)的，左偏樹本身除了可以迅速找到最小節(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è)功能的，它們并沒有將擁有權(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)用也是很常見的。設(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ì)剩下它的兩棵子樹，它們都是左偏樹，我們先把它們合并成一棵新的左偏樹。p■Merge(left(x),right(x))現(xiàn)在p指向了這顆新的左偏樹，如果我們刪除的是根節(jié)點(diǎn)，此時(shí)任務(wù)已經(jīng)完成了。不過(guò)，如果被刪除節(jié)點(diǎn)x不是根節(jié)點(diǎn)就有點(diǎn)麻煩了。這時(shí)p指向的新樹的距離有可能比原來(lái)X的距離要大或小，這勢(shì)必有可能影響原來(lái)x的父節(jié)點(diǎn)q的距離，因?yàn)閝現(xiàn)在成為新樹p的父節(jié)點(diǎn)了。于是就要仿照合并操作里面的做法，對(duì)q的左右子樹作出調(diào)整，并更新q的距離。這一過(guò)程引起了連鎖反應(yīng)，我們要順著q的父節(jié)點(diǎn)鏈一直往上進(jìn)行調(diào)整。新樹p的距離為dist(p)，如果dist(p)+l等于q的原有距離dist(q)，那么不管p是q的左子樹還是右子樹，我們都不需要對(duì)q進(jìn)行任何調(diào)整，此時(shí)刪除操作也就完成了。如果dist(p)+1小于q的原有距離dist(q)，那么q的距離必須調(diào)整為dist(p)+1，而且如果p是左子樹的話，說(shuō)明q的左子樹距離比右子樹小，必須交換子樹。由于q的距離減少了，所以q的父節(jié)點(diǎn)也要做出同樣的處理。剩下就是另外一種情況了，那就是p的距離增大了，使得dist(p)+1大于q的原有距離dist(q)。在這種情況下，如果p是左子樹，那么q的距離不會(huì)改變，此時(shí)刪除操作也可以結(jié)束了。如果p是右子樹，這時(shí)有兩種可能：一種是p的距離仍小于等于q的左子樹距離，這時(shí)我們直接調(diào)整q的距離就行了；另一種是p的距離大于q的左子樹距離，這時(shí)我們需要交換q的左右子樹并調(diào)整q的距離，交換完了以后q的右子樹是原來(lái)的左子樹，它的距離加1只能等于或大于q的原有距離，如果等于成立，刪除操作可以結(jié)束了，否則q的距離將增大，我們還要對(duì)q的父節(jié)點(diǎn)做出相同的處理。刪除任意已知節(jié)點(diǎn)操作的代碼如下：ProcedureDelete(x)q—parent(x)p—Merge(left(x),right(x))parent(p)—qfq豐NULLandleft(q)=xThenleft(q)—pIfq主NULLandright(q)=xThenright(q)—pWhileq豐NULLDoIfdist(left(q))<dist(right(q))Thenswap(left(q),right(q))Ifdist(right(q))+1=dist(q)ThenExitProceduredist(q)—dist(right(q))+1p—qq—parent(q)EndWhileEndProcedure下面分兩種情況討論刪除操作的時(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的左子樹，否則會(huì)出現(xiàn)q的右子樹距離縮小了，但是加1以后卻大于q的距離的情況，不符合左偏樹的性質(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的距離增大了。在這種情況下，我們將必然一直從右子樹向上調(diào)整，直至q為空或p是q的左子樹時(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的左子樹。這三種情況都不會(huì)導(dǎo)致另一情況發(fā)生。直觀上來(lái)講，如果合并后的新子樹導(dǎo)致了父節(jié)點(diǎn)的一系列距離調(diào)整的話，要么就一直是往小調(diào)整，要么是一直往大調(diào)整，不會(huì)出現(xiàn)交替的情況。我們已經(jīng)知道合并出新子樹p的復(fù)雜度是O(logn)，向上調(diào)整距離的復(fù)雜度也是O(logn)，故刪除操作的最壞情況的時(shí)間復(fù)雜度是O(logn)。如果左偏樹非常傾斜，實(shí)際應(yīng)用情況下要比這個(gè)快得多。3.6小結(jié)本章介紹了左偏樹的各種操作，我們可以看到，左偏樹作為可并堆的實(shí)現(xiàn)，它的各種操作性能都十分優(yōu)秀，且編程復(fù)雜度比較低，可以說(shuō)是一個(gè)“性價(jià)比”十分高的數(shù)據(jù)結(jié)構(gòu)。左偏樹之所以是很好的可并堆實(shí)現(xiàn)，是因?yàn)樗軌虿蹲降骄哂卸研再|(zhì)的二叉樹里面的一些其它有用信息，沒有將這些信息浪費(fèi)掉。根據(jù)堆性質(zhì)，我們知道，從根節(jié)點(diǎn)向下到任何一個(gè)外節(jié)點(diǎn)的路徑都是有序的。存在越長(zhǎng)的路徑，說(shuō)明樹的整體有序性越強(qiáng)，與平衡樹不同(平衡樹根本不允許有很長(zhǎng)的路徑)，左偏樹盡大約一半的可能保留了這個(gè)長(zhǎng)度，并將它甩向左側(cè)，利用它來(lái)縮短節(jié)點(diǎn)的距離以提高性能。這里我們不進(jìn)行嚴(yán)格的討論，左偏樹作為一個(gè)例子大致告訴我們：放棄已有的信息意味著算法性能上的犧牲。下面是最好的左偏樹：有序表(插入操作是按逆序發(fā)生的，自然的有序性被保留了)和最壞的左偏樹：平衡樹(插入操作是按正序發(fā)生的，自然的有序性完全被放棄了)。四、左偏樹的應(yīng)用4.1例一一數(shù)字序列(Baltic2004)[問題描述]題目來(lái)源：BalticOI2004Day1,題目來(lái)源：BalticOI2004Day1,Sequence本文對(duì)原題略微做了改動(dòng)丫為了方便討論和程序?qū)崿F(xiàn)，本文中提到的中位數(shù)，都是指數(shù)列中第Ln/2」大的數(shù)J這里我們認(rèn)為q[m+1]=n+1給定一個(gè)整數(shù)序列a1,a2,,an，求一個(gè)不下降序列b1<b2S...Sbn，使得數(shù)列｛aj和｛bj的各項(xiàng)之差的絕對(duì)值之和la1-b1l+la2-b2|+…+[a』bj最小。[數(shù)據(jù)規(guī)模]1<n<106,0<ai<2*109[初步分析]我們先來(lái)看看兩個(gè)最特殊的情況：a[1]<a[2]<...<a[n],在這種情況下，顯然最優(yōu)解為b[i]=a[i]；a[1]>a[2]>.>a[n],這時(shí)，最優(yōu)解為b[i]=x,其中x是數(shù)列a的中位數(shù)丫。于是我們可以初步建立起這樣一個(gè)思路：把1…n劃分成m個(gè)區(qū)間：[q[1],q[2]-1],[q[2],q[3]-1],……，[q[m],q[m+1]-1]t。每個(gè)區(qū)間對(duì)應(yīng)一個(gè)解，b[q[i]]=b[q[i]+1]=…=b[q[i+1]-1]=w[i]，其中w[i]為a[q[i]],a[q[i]+1],...,a[q[i+1]-1]的中位數(shù)。顯然，在上面第一種情況下m=n,q[i]=i；在第二種情況下m=1,q[1]=1。這樣的想法究竟對(duì)不對(duì)呢？應(yīng)該怎樣實(shí)現(xiàn)？若某序列前半部分a[1],a[2],.,a[n]的最優(yōu)解為(u,u,...,u),后半部分a[n+1],a[n+2],...,a[m]的最優(yōu)解為(v,v,那么整個(gè)序列的最優(yōu)解是什么呢？若u<V,顯然整個(gè)序列的最優(yōu)解為(u,u,...,u,v,v,...,v)。否則，設(shè)整個(gè)序列的最優(yōu)解為(b[1],b[2],…,b[m]),貝q顯然b[n]<u(否則我們把前半部分的解(b[1],b[2],...,b[n])改為(u,u,...,u),由題設(shè)知整個(gè)序列的解不會(huì)變壞)，同理b[n+1]>V。接下來(lái)，我們將看到下面這個(gè)事實(shí)：對(duì)于任意一個(gè)序列a[1],a[2],...,a[n],如果最優(yōu)解為(u,u,...,u),那么在滿足u<u'<b[1]或b[n]<u'<u的情況下,(b[1],b[2],...,b[n])不會(huì)比(u，,...,u')更優(yōu)。我們用歸納法證明u<u'<b[1]的情況，b[n]<u'<u的情況可以類似證明。當(dāng)n=1時(shí)，u=a[1]，命題顯然成立。當(dāng)n>1時(shí)，假設(shè)對(duì)于任意長(zhǎng)度小于n的序列命題都成立，現(xiàn)在證明對(duì)于長(zhǎng)度為n的序列命題也成立。首先把(b[1],b[2],…b[n])改為(b[1],b[1],…b[1]),這一改動(dòng)將不會(huì)導(dǎo)致解變壞，因?yàn)槿绻庾儔牧?，由歸納假設(shè)可知a[2],a[3],...,a[n]的中位數(shù)w>u,這樣的話，最優(yōu)解就應(yīng)該為(u,u，…，u,w,W，…，W),矛盾。然后我們?cè)侔?b[1],b[1],...,b[1])改為(u，，卍,...,u'),由于|a[1]-x|+|a[2]-x|+…+|a[n]-x|的幾何意義為數(shù)軸上點(diǎn)x到點(diǎn)a[1],a[2],...a[n]的距離之和，且u<uf<b[1]，顯然點(diǎn)山到各點(diǎn)的距離之和不會(huì)比點(diǎn)b[1]到各點(diǎn)的距離之和大，也就是說(shuō)，(b[l],b[l],...,b[n])不會(huì)比(v,v,...,v)更優(yōu)。(證畢)再回到之前的論述，由于b[n]<u,作為上述事實(shí)的結(jié)論，我們可以得知，將(b[1],b[2],…,b[n])改為(b[n],b[n],…,b[n])，再將(b[n+1],b[n+2],…,b[m])改為(b[n+1],b[n+1],...,b[n+1]),并不會(huì)使解變壞。也就是說(shuō)，整個(gè)序列的最優(yōu)解為(b[n],b[n],...,b[n],b[n+1],b[n+1],...,b[n+1])。再考慮一下該解的幾何意義，設(shè)整個(gè)序列的中位數(shù)為w,則顯然令b[n]=b[n+1]=w將得到整個(gè)序列的最優(yōu)解，即最優(yōu)解為(w,w,...,w)。分析到這里，我們一開始的想法已經(jīng)有了理論依據(jù)，算法也不難構(gòu)思了。[算法描述]延續(xù)我們一開始的思路,假設(shè)我們已經(jīng)找到前k個(gè)數(shù)a[1],a[2],…，a[k](kvn)的最優(yōu)解，得到m個(gè)區(qū)間組成的隊(duì)列，對(duì)應(yīng)的解為(w[1],w[2],...,w[m])，現(xiàn)在要加入a[k+1]，并求出前k+1個(gè)數(shù)的最優(yōu)解。首先我們把a(bǔ)[k+1]作為一個(gè)新區(qū)間直接加入隊(duì)尾，令w[m+1]=a[k+1]，然后不斷檢查隊(duì)尾兩個(gè)區(qū)間的解w[m]和w[m+1]，如果w[m]>w[m+1]，我們需要將最后兩個(gè)區(qū)間合并，并找出新區(qū)間的最優(yōu)解(也就是序列a中，下標(biāo)在這個(gè)新區(qū)間內(nèi)的各項(xiàng)的中位數(shù))。重復(fù)這個(gè)合并過(guò)程，直至w[1]<w[2]<...<w[m]時(shí)結(jié)束，然后繼續(xù)處理下一個(gè)數(shù)。這個(gè)算法的正確性前面已經(jīng)論證過(guò)了，現(xiàn)在我們需要考慮一下數(shù)據(jù)結(jié)構(gòu)的選取。算法中涉及到以下兩種操作：合并兩個(gè)有序集以及查詢某個(gè)有序集內(nèi)的中位數(shù)。能較高效地支持這兩種操作的數(shù)據(jù)結(jié)構(gòu)有不少，一個(gè)比較明顯的例子是二叉檢索樹(BST)，它的詢問操作復(fù)雜度是O(logn)，但合并操作不甚理想，采用啟發(fā)式合并，總時(shí)間復(fù)雜度為O(nlog2n)。有沒有更好的選擇呢？通過(guò)進(jìn)一步分析，我們發(fā)現(xiàn)，只有當(dāng)某一區(qū)間內(nèi)的中位數(shù)比后一區(qū)間內(nèi)的中位數(shù)大時(shí)，合并操作才會(huì)發(fā)生，也就是說(shuō)，任一區(qū)間與后面的區(qū)間合并后，該區(qū)間內(nèi)的中位數(shù)不會(huì)變大。于是我們可以用最大堆來(lái)維護(hù)每個(gè)區(qū)間內(nèi)的中位數(shù)，當(dāng)堆中的元素大于該區(qū)間內(nèi)元素的一半時(shí)，刪除堆頂元素，這樣堆中的元素始終為區(qū)間內(nèi)較小的一半元素，堆頂元素即為該區(qū)間內(nèi)的中位數(shù)?？紤]到我們必須高效地完成合并操作，左偏樹是一個(gè)理想的選擇前面介紹的左偏樹是最小堆，但在本題中，顯然只需把左偏樹的性質(zhì)稍做修改，就可以實(shí)現(xiàn)最大堆了。左偏樹的詢問操作時(shí)間復(fù)雜度為0(1)，刪除和合并操作時(shí)間復(fù)雜度都是O(logn)，而詢問操作和合并操作少于n次，刪除操作不超過(guò)n/2次(因?yàn)閯h除操作只會(huì)在合并兩個(gè)元素個(gè)數(shù)為奇數(shù)的堆時(shí)發(fā)生)，因此用左偏樹實(shí)現(xiàn)，可以把算法的時(shí)間復(fù)雜度降為O(nlogn)。前面介紹的左偏樹是最小堆，但在本題中，顯然只需把左偏樹的性質(zhì)稍做修改，就可以實(shí)現(xiàn)最大堆了[小結(jié)]這道題的解題過(guò)程對(duì)我們頗有啟示。在應(yīng)用左偏樹解題時(shí)，我們往往會(huì)覺得題目無(wú)從下手，甚至與左偏樹毫無(wú)關(guān)系，但只要我們對(duì)題目深入分析，加以適當(dāng)?shù)霓D(zhuǎn)化，問題終究會(huì)迎刃而解。這需要我們具有敏捷的思維以及良好的題感。用左偏樹解本題，相比較于前面BST的解法，時(shí)間復(fù)雜度和編程復(fù)雜度更低，這使我們不得不感嘆于左偏樹的神奇威力。這不是說(shuō)左偏樹就一定是最好的解法，就本題來(lái)說(shuō)，解法有很多種，光是可并堆的解法，就可以用多種數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)，但左偏樹相對(duì)于它們，還是有一定的優(yōu)勢(shì)的，這將在下一章詳細(xì)討論。五、左偏樹與各種可并堆的比較我們知道，左偏樹是一種可并堆的實(shí)現(xiàn)。但是為什么我們要用左偏樹實(shí)現(xiàn)可并堆呢？左偏樹相對(duì)于其他可并堆有什么優(yōu)點(diǎn)？本章將就這個(gè)問題展開討論，介紹各種可并堆的特點(diǎn)，并對(duì)它們做出比較。5.1左偏樹的變種斜堆這里我們要介紹左偏樹的一個(gè)變種斜堆(SkewHeap)。斜堆是一棵堆有序的二叉樹，但是它不滿足左偏性質(zhì)，或者說(shuō)，斜堆根本就沒有“距離”這個(gè)概念一一它不需要記錄任何一個(gè)節(jié)點(diǎn)的距離。從結(jié)構(gòu)上來(lái)說(shuō)，所有的左偏樹都是斜堆，但反之不然。類似于左偏樹，斜堆的各種操作也是在合并操作的基礎(chǔ)上完成的，因此這里只介紹斜堆的合并操作，其他操作讀者都可以仿照左偏樹完成。斜堆合并操作的遞歸合并過(guò)程和左偏樹完全一樣。假設(shè)我們要合并A和B兩個(gè)斜堆，且A的根節(jié)點(diǎn)比B的根節(jié)點(diǎn)小，我們只需要把A的根節(jié)點(diǎn)作為合并后新堆的根節(jié)點(diǎn)，并將A的右子樹與B合并。由于合并都是沿著最右路徑進(jìn)行的，經(jīng)過(guò)合并之后，新堆的最右路徑長(zhǎng)度必然增加，這會(huì)影響下一次合并的效率。為了解決這一問題，左偏樹在進(jìn)行合并的同時(shí)，檢查最右路徑節(jié)點(diǎn)的距離，并通過(guò)交換左右子樹，使整棵樹的最右路徑長(zhǎng)度非常小。然而斜堆不記錄節(jié)點(diǎn)的距離，那么應(yīng)該怎樣維護(hù)最右路徑呢？我們采取的辦法是，從下往上，沿著合并的路徑，在每個(gè)節(jié)點(diǎn)處都交換左右子樹。下面是斜堆合并操作的代碼：FunctionMerge(A,B)IfA=NULLThenreturnBIfB=NULLThenreturnAIfkey(B)<key(A)Thenswap(A,B)right(A)■Merge(right(A),B)swap(left(A),right(A))returnAEndFunction斜堆的這種維護(hù)方法也是行之有效的。通過(guò)不斷交換左右子樹，斜堆把最右路徑甩向左邊了。可以證明，斜堆合并操作的平攤時(shí)間復(fù)雜度為O(logn)。這里略去詳細(xì)的復(fù)雜度分析，感興趣的讀者可以自行參考相關(guān)的資料。前面說(shuō)過(guò)，斜堆的其他各種操作都和左偏樹類似，因此斜堆各項(xiàng)操作的平攤時(shí)間復(fù)雜度都與左偏樹相同。在空間上，由于斜堆不用記錄節(jié)點(diǎn)的距離，因此它比左偏樹的空間需求小一點(diǎn)。至于編程復(fù)雜度，兩者都十分的低，不過(guò)斜堆的代碼還是要比左偏樹稍微簡(jiǎn)潔一些。至于斜堆的不足，大概可以算是它單次合并操作的時(shí)間復(fù)雜度可能退化為0(n),不過(guò)通常這并不影響算法的總時(shí)間復(fù)雜度?？偟膩?lái)說(shuō)，斜堆作為左偏樹的變種，與左偏樹并無(wú)優(yōu)劣之分。在斜堆能派上用場(chǎng)的地方，左偏樹同樣能出色地實(shí)現(xiàn)算法。斜堆與左偏樹之間的關(guān)系，可以類比于伸展樹與AVL樹之間的關(guān)系，只不過(guò)前兩者的編程復(fù)雜度，并沒有多大的差別。5.2左偏樹與二叉堆的比較二叉堆大概是我們最常用的一種優(yōu)先隊(duì)列了，它具有簡(jiǎn)潔，高效的特點(diǎn)，應(yīng)用十分廣泛。二叉堆和左偏樹相比，除了合并操作外的各種操作，時(shí)間復(fù)雜度都一樣，但在實(shí)際測(cè)試中，二叉堆往往比左偏樹快一些。在空間上，由于二叉堆是完全二叉樹，用數(shù)組表示法，可以剩下左右子樹指針的空間，在這點(diǎn)上左偏樹又吃了一虧。介紹了二叉堆的優(yōu)點(diǎn)，下面的這兩個(gè)缺點(diǎn)也是不容忽視的：在進(jìn)行插入、刪除等操作后，二叉堆中元素的物理位置會(huì)發(fā)生改變。二叉堆的合并操作太慢，時(shí)間復(fù)雜度高達(dá)0(n)。當(dāng)元素本身所占空間比較大時(shí)，頻繁地移動(dòng)元素物理位置將會(huì)影響時(shí)間效率。而有些時(shí)候，我們需要隨時(shí)掌握某些元素的物理位置，以便對(duì)它進(jìn)行訪問或修改(比如實(shí)現(xiàn)刪除任意已知節(jié)點(diǎn)操作)，這時(shí)，二叉堆的第一個(gè)缺點(diǎn)將給我們?cè)斐梢欢ǖ穆闊覀儾坏貌煌ㄟ^(guò)增加元素指針等手段來(lái)解決這個(gè)問題。而二叉堆合并效率的低下則是由其本身性質(zhì)所造成的，采用啟發(fā)式合并可以作為大多數(shù)情況下的一個(gè)優(yōu)化，但效果仍不能令人滿意。至于二叉堆空間上的優(yōu)勢(shì)，也不是絕對(duì)的。數(shù)組表示法并不是在任何場(chǎng)合都適用的，比如當(dāng)我們需要?jiǎng)討B(tài)維護(hù)多個(gè)優(yōu)先隊(duì)列的時(shí)候，二叉堆不得不使用傳統(tǒng)的指針表示法，這時(shí)二叉堆和左偏樹在空間上就相差無(wú)幾了。二叉堆的上述特點(diǎn)，決定了它不適合作為可并堆的實(shí)現(xiàn)?？陀^的說(shuō)，需要實(shí)現(xiàn)可并堆的題目在競(jìng)賽中并不多見，不過(guò)當(dāng)我們遇到這類題目或者某些特殊的情況時(shí)，左偏樹將會(huì)是比二叉堆更好的選擇。5.3左偏樹與其他可并堆的比較前面已經(jīng)提到過(guò)，可并堆可以用多種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，左偏樹并非唯一的選擇。二項(xiàng)堆，F(xiàn)ibonacci堆都是時(shí)間效率十分優(yōu)秀的可并堆。二項(xiàng)堆是由若干棵深度不同的二項(xiàng)樹組成的森林。深度為k的二項(xiàng)樹Bk由兩棵二項(xiàng)樹Bk1連接根節(jié)點(diǎn)而成，有2k個(gè)節(jié)點(diǎn)，并且滿足堆性質(zhì)。二項(xiàng)樹組成二項(xiàng)堆的形式可以看作總節(jié)點(diǎn)數(shù)n的二進(jìn)制表示形式，兩個(gè)二項(xiàng)堆的合并可以看作二進(jìn)制數(shù)的加法，這點(diǎn)很有啟發(fā)意義。與左偏樹類似，二項(xiàng)堆的各種操作也是在合并操作的基礎(chǔ)上完成的。二項(xiàng)堆的結(jié)構(gòu)和性質(zhì)決定了它可以很高效地完成合并操作，與左偏樹相比，雖然復(fù)雜度相同，但一般實(shí)際情況下二項(xiàng)堆比較快。但二項(xiàng)樹實(shí)現(xiàn)取最小節(jié)點(diǎn)操作需要檢查所有二項(xiàng)樹的根節(jié)點(diǎn)，因此這項(xiàng)操作時(shí)間復(fù)雜度比左偏樹高這里其實(shí)有一個(gè)辦法可以解決這個(gè)問題，就是隨時(shí)記錄最小節(jié)點(diǎn)，并只在插入、刪除以及合并等操作進(jìn)行的時(shí)候更新該記錄，這樣二項(xiàng)堆的取最小節(jié)點(diǎn)操作時(shí)間復(fù)雜度可以降為0(1)這里其實(shí)有一個(gè)辦法可以解決這個(gè)問題，就是隨時(shí)記錄最小節(jié)點(diǎn)，并只在插入、刪除以及合并等操作進(jìn)行的時(shí)候更新該記錄，這樣二項(xiàng)堆的取最小節(jié)點(diǎn)操作時(shí)間復(fù)雜度可以降為0(1)丫表中Fibonacci堆的“刪除最小節(jié)點(diǎn)”和“刪除任意節(jié)點(diǎn)”兩個(gè)操作的時(shí)間復(fù)雜度均為平攤時(shí)間復(fù)雜度，而二項(xiàng)堆“插入”操作的平均時(shí)間復(fù)雜度為0(1),表中給出的是最壞時(shí)間復(fù)雜度Fibonacci堆是一個(gè)很復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，與二項(xiàng)堆一樣，它也是由一組堆有序的樹構(gòu)成的。所不同的是，F(xiàn)ibonacci堆的樹不一定是二項(xiàng)樹，而且這些樹是無(wú)序的，且樹中兄弟節(jié)點(diǎn)的聯(lián)系用雙向循環(huán)鏈表來(lái)表示。Fibonacci堆實(shí)現(xiàn)插入操作和合并操作只是簡(jiǎn)單地將兩個(gè)Fibonacci堆的根表連在一起，因此這兩個(gè)操作比其他可并堆都快。但在刪除操作時(shí)，我們需要對(duì)Fibonacci堆進(jìn)行維護(hù)，合并所有度數(shù)相同的樹，這一步異常復(fù)雜，并且是最慢的。有關(guān)二項(xiàng)堆和Fibonacci堆的詳細(xì)介紹，有興趣的讀者可以參考相關(guān)資料，本文不再贅述。下表列出了各種可并堆的各項(xiàng)操作的時(shí)間復(fù)雜度丫，已及它們的空間需求和編程復(fù)雜度。項(xiàng)目二叉堆左偏樹二項(xiàng)堆Fibonacci堆構(gòu)建0(n)0(n)0(n)0(n)插入O(logn)O(logn)0(logn)0(1)取最小節(jié)點(diǎn)0(1)0(1)0(logn)0(1)刪除最小節(jié)點(diǎn)O(logn)O(logn)0(logn)0(logn)刪除任意節(jié)點(diǎn)O(logn)0(logn)0(logn)0(logn)合并0(n)0(logn)0(logn)0(1)空間需求最小較小一般較大編程復(fù)雜度最低較低較咼很高從表中我們可以看出，F(xiàn)ibonacci堆的時(shí)間復(fù)雜度非常低，如果我們不需要進(jìn)行頻繁的刪除操作，用Fibonacci堆實(shí)現(xiàn)可并堆將會(huì)降低算法的時(shí)間復(fù)雜度。但實(shí)際上，刪除操作往往是很重要的操作，而Fibonacci堆的刪除操作比表中其它可并堆都慢，至于它的空間需求，也大得使人望而卻步。更槽糕的是Fibonacci堆的編程復(fù)雜度太高了，在競(jìng)賽中使用實(shí)在是不理智的行為。至于二項(xiàng)堆，雖然各項(xiàng)操作的時(shí)間效率都十分優(yōu)秀，但空間需求和編程復(fù)雜度仍然比不上左偏樹。和左偏樹相比，二項(xiàng)堆在時(shí)間效率上的優(yōu)勢(shì)微乎其微，用左偏樹代替二項(xiàng)堆，的確會(huì)犧牲一些算法性能，但換來(lái)的卻是簡(jiǎn)潔的代碼，便于實(shí)現(xiàn)和調(diào)試的程序。在時(shí)間有限的競(jìng)賽中，左偏樹無(wú)疑是更好的選擇。最后，我們應(yīng)該認(rèn)識(shí)到，雖然二項(xiàng)堆和Fibonacci堆某些操作的時(shí)間復(fù)雜度比左偏樹低，但是在實(shí)際應(yīng)用中，那些時(shí)間復(fù)雜度較高的操作往往會(huì)成為算法的瓶頸。比如前面的例題《數(shù)字序列》改用二項(xiàng)堆或Fibonacci堆實(shí)現(xiàn)，總時(shí)間復(fù)雜度仍為O(nlogn)，并不能起到降低算法時(shí)間復(fù)雜度的作用，實(shí)現(xiàn)難度反而增加了不少。六、總結(jié)至此，我們已經(jīng)對(duì)左偏樹有了深刻的認(rèn)識(shí)。左偏樹在時(shí)間效率上不如二項(xiàng)堆和Fibonacci堆，在空間效率上不如二叉堆，這樣看來(lái)左偏樹沒有任何獨(dú)樹一幟的地方，似乎是個(gè)相當(dāng)平庸的數(shù)據(jù)結(jié)構(gòu)，但其實(shí)這正是左偏樹的優(yōu)勢(shì)所在。正所謂“魚與熊掌不可兼得”，時(shí)間復(fù)雜度、空間復(fù)雜度和編程復(fù)雜度，這三者之間很多時(shí)候是矛盾的。Fibonacci堆時(shí)間復(fù)雜度最低，但編程復(fù)雜度讓人無(wú)法接受;二叉堆的空間復(fù)雜度和編程復(fù)雜度都很低，但時(shí)間復(fù)雜度卻是它的致命弱點(diǎn)。左偏樹很好地協(xié)調(diào)了三者之間的矛盾，并且在存儲(chǔ)性質(zhì)上，沒有二叉堆那樣的缺陷,因此左偏樹的適用范圍十分廣。左偏樹不但可以高效方便地實(shí)現(xiàn)可并堆，更可以作為二叉堆的替代品，應(yīng)用于各種優(yōu)先隊(duì)列，很多時(shí)候甚至比二叉堆更方便。【感謝】感謝余江偉同學(xué)及阮志遠(yuǎn)老師的熱心幫助和修改意見。【參考文獻(xiàn)】傅清祥，王曉東算法與數(shù)據(jù)結(jié)構(gòu)(第二版)電子工業(yè)出版社ThomasH.Cormen,CharlesE.Leiserson,RonaldL.Rivest,CliffordSteinIntroductiontoAlgorithms(SecondEdition)TheMITPressMarkAllenWeissDataStructuresandAlgorithmAnalysisinC(SecondEdition)PearsonEducation【附錄】附錄I:例題《數(shù)字序列》的原題SEQUENCEShortformulation.Thenumbersequenceisgiven.Yourtaskistoconstructtheincreasingsequencethatapproximatesthegivenoneinthebestway.Thebestapproximatingsequenceisthesequencewiththeleasttotaldeviationfromthegivensequence.Moreprecisely.Lett],5…，t”isthegivennumbersequence.Yourtaskistoconstructtheincreasingnumbersequencez]<z2<…'zn.ThesumIt-zI+|L-z」+…+|tT-zjshouldbeaminimalfeasible.11221NNInputThereistheintegerN(1<N<1000000)inthefirstlineofinputfileseq.in.EachofthenextNlinescontainssingleinteger—thegivensequenceelement.ThereistKinthe(K+1)-thline.Anyelementissatisfyingtorelation0<tK<2000000000.OutputThefirstlineofoutputfileseq.outmustcontainthesingleinteger—theminimalpossibletotaldeviation.EachofthenextNlinesmustcontainsingleinteger—therecurrentelementofthebestapproximatingsequence.Ifthereareseveralsolutions,