本節書摘來自華章計算機《程式設計解題政策》一書中的第1章，第1.6節,作者：吳永輝 王建德 更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。
優先隊列在程式設計競賽中十分常見，在統計問題、最值問題、模拟問題和貪心問題等類型的題目中，優先隊列都有着廣泛的應用。二叉堆是一種常用的優先隊列，它程式設計簡單、效率高，但如果問題需要對兩個優先隊列進行合并，二叉堆的效率就無法令人滿意了。為了解決這個問題，我們引入了左偏樹。
1.6.1 左偏樹的定義和性質
在介紹左偏樹之前，我們先來回顧一下優先隊列和可并堆的概念。
優先隊列(priority queue)：一種抽象資料類型(adt)。它是一種容器，裡面有一些元素，這些元素也稱為隊列中的節點(node)。優先隊列的節點至少要包含一種性質：有序性，也就是說任意兩個節點可以比較大小。為了具體起見，我們假設這些節點中都包含一個鍵值(key)，節點的大小通過比較它們的鍵值而定。優先隊列有三個基本的操作：插入節點(insert)、取得最小節點(minimum)和删除最小節點(delete-min)。
可并堆(mergeable heap)：也是一種抽象資料類型，它除了支援優先隊列的三個基本操作，還支援一個額外的操作——合并操作：h=merge(h1，h2)，該操作構造并傳回一個包含h1和h2所有元素的新堆h。
左偏樹(leftist tree)：一種可并堆的實作。左偏樹是一棵二叉樹，它的節點除了和二叉樹的節點一樣具有左右子樹指針(left，right)外，還有兩個屬性：鍵值和距離(dist)。鍵值是用于比較節點的大小，而距離是在外節點的基礎上提出的。距離和外節點的定義：
外節點(external node)：節點i稱為外節點當且僅當節點i的左子樹或右子樹為空(left(i)=null或right(i)=null)。
節點i的距離(dist(i))：節點i到它的後代中，最近的外節點所經過的邊數。特别地，如果節點i本身是外節點，則它的距離為0；而空節點的距離規定為-1(dist(null)=-1)。左偏樹的距離指的是該樹根節點的距離。
左偏樹的定義是由其本身具備的兩個基本特征引出的：
堆特征：節點的鍵值小于或等于它的左右子節點的鍵值，即key(i)≤key(parent(i))。符合堆特征的樹是堆有序的(heap-ordered)。有了堆特征，我們可以知道左偏樹的根節點是整棵樹的最小節點，于是我們可以在o(1)的時間内完成取最小節點操作。
左偏特征：節點的左子節點的距離不小于右子節點的距離，即dist(left(i))≥dist(right(i))。
左偏特征是為了使我們在插入節點和删除最小節點後，以更小的代價維持堆特征。在後面我們就會看到它的作用。
由于左偏樹的每一個節點具有堆特征和左偏特征，是以左偏樹任一節點的左右子樹都是左偏樹。由堆特征和左偏特征可以引出左偏樹的定義：（左偏樹是具有左偏特征的堆有序二叉樹）。
圖1.6-1是一棵左偏樹。
https://yqfile.alicdn.com/78ca6195a8e2afc7c2268b8a53cba12b159db553.png" >
下面，我們來分析左偏樹的性質。我們知道，左偏樹的任一個非葉節點必須經由它的子節點才能到達外節點。由于左偏特征，一個節點的距離實際上就是這個節點一直沿它的右邊到達一個外節點所經過的邊數，是以引出：
【性質1.6-1】 節點的距離等于它的右子節點的距離加1，即dist(i)=dist(right(i))+1。
外節點的距離為0，由于左偏特征，它的右子節點必為空節點。為了滿足性質1.6-1，故前面規定空節點的距離為-1。
在我們的印象中，平衡樹是具有非常小的深度的，這也意味着到達任何一個節點所經過的邊數很少。左偏樹并不是為了快速通路所有節點而設計的，它的目的是快速通路最小節點以及在對樹修改後快速恢複堆特征。從圖1.6-1中我們可以看到它并不平衡，由于左偏特征的緣故，它的結構偏向左側，不過距離的概念和樹的深度并不同，左偏樹并不意味着左子樹的節點數或是深度一定大于右子樹。下面，我們來讨論左偏樹的距離和節點數的關系。
【引理1.6-1】 若左偏樹的距離為一定值，則節點數最少的左偏樹是完全二叉樹。
證明：由左偏特征可知，當且僅當對于一棵左偏樹中的每個節點i，都有dist(left(i))=dist(right(i))時，該左偏樹的節點數最少。顯然具有這樣性質的二叉樹是完全二叉樹。
【定理1.6-1】 若一棵左偏樹的距離為k，則這棵左偏樹至少有2k+1-1個節點。
證明：由引理1.6-1可知，當這樣的左偏樹節點數最少的時候，是一棵完全二叉樹。距離為k的完全二叉樹高度也為k，節點數為2k+1-1，是以距離為k的左偏樹至少有2k+1-1個節點。
作為定理1.6-1的推論，我們有：
【性質1.6-2】 一棵n個節點的左偏樹距離最多為log2(n+1)」-1。
證明：設一棵n個節點的左偏樹距離為k，由定理1.6-1可知，n≥2k+1-1，是以k≤log2(n+1)」-1。
有了左偏樹的堆特征、左偏特征和上面兩個性質，我們可以開始讨論左偏樹的操作了。
1.6.2 左偏樹的操作
首先，我們定義左偏樹節點的資料結構。設：
左偏樹的操作包括建構左偏樹、合并左偏樹、插入新節點、删除最小節點和删除任意節點。
1.建構左偏樹
将n個節點建構成一棵左偏樹，這也是一個常用的操作。建構方法有兩種：
建構方法1：逐個節點插入，時間複雜度為o(nlog2n)。
建構方法2：仿照二叉堆的建構算法，圖1.6-2給出了範例。
https://yqfile.alicdn.com/1ac63e1dc10f839021c9b0282ef4eb6a8f981be3.png" >
下面分析算法的時間複雜度。假設n=2k，則：
前n2次合并的是兩棵隻有1個節點的左偏樹。
接下來的n4次合并的是兩棵有2個節點的左偏樹。
接下來的n8次合并的是兩棵有4個節點的左偏樹。
……
接下來的n2i次合并的是兩棵有2i-1個節點的左偏樹。
合并兩棵2i個節點的左偏樹時間複雜度為o(i)，是以算法總的時間複雜度為
2.合并左偏樹(merge(a，b))
由于合并操作是插入和删除操作的基礎，是以我們做重點讨論：
merge(a，b)把a、b兩棵左偏樹合并，傳回一棵包含a和b中所有元素的左偏樹c。一棵左偏樹用它的根節點的指針表示(見圖1.6-3)。
在合并操作中，最簡單的情況是其中一棵樹為空(也就是，該樹根節點指針為null)。這時我們隻需要傳回另一棵樹。
若a和b都非空，我們假設a的根節點小于等于b的根節點(否則交換a、b)，把a的根節點作為新樹c的根節點，剩下的事就是合并a的右子樹right(a)和b了(見圖1.6-4)。
合并了right(a)和b之後，right(a)的距離可能會變大，當right(a)的距離大于left(a)的距離時，左偏樹的左偏特征會被破壞(見圖1.6-5)。在這種情況下，我們隻須交換left(a)和right(a)。
最後，由于right(a)的距離可能發生改變，我們必須更新a的距離：
不難驗證，經這樣合并後的樹c符合堆特征和左偏特征，是以是一棵左偏樹。至此左偏樹的合并就完成了。圖1.6-6是一個合并過程的範例(節點上方的數字為距離值)。
下面分析合并操作的時間複雜度。由上所述，每一次遞歸合并的開始，都需要分解其中一棵樹，總是把分解出的右子樹參加下一步的合并。根據性質1.6-1，一棵樹的距離決定于其右子樹的距離，而右子樹的距離在每次分解中遞減，是以每棵樹a或b被分解的次數分别不會超過它們各自的距離。根據性質1.6-2，分解的次數不會超過log2(n1+1)」+log2(n2+1)」-2，其中n1和n2分别為左偏樹a和b的節點個數。是以合并操作最壞情況下的時間複雜度為o(log2(n1+1)」+log2(n2+1)」-2)=o(log2n1+log2n2)。
3.插入節點(insert(val))
單節點的樹一定是左偏樹，是以向左偏樹插入一個值為val的節點可以看作是對兩棵左偏樹的合并(見圖1.6-7)。
下面是插入新節點的代碼：
由于合并的其中一棵樹隻有一個節點，是以插入新節點操作的時間複雜度是o(log2n)。
4.删除左偏樹的最小節點(deleteroot())
由堆特征，我們知道，左偏樹的根節點是最小節點。在删除根節點後，剩下的兩棵子樹都是左偏樹，需要把它們合并(見圖1.6-8)。
删除最小節點操作的代碼也非常簡單：
由于删除最小節點後隻需進行一次合并，是以删除最小節點的時間複雜度也為o(log2n)。
5.删除任意已知節點x(delete(x))
我們在這裡之是以強調“已知”，是因為任意節點x并不是根據它的鍵值找出來的，左偏樹本身除了可以迅速找到最小節點外，不能有效地搜尋指定鍵值的節點。例如不能要求删除所有鍵值為100的節點。
前面說過，優先隊列是一種容器。對于通常的容器來說，一旦節點被放進去以後，容器就完全擁有了這個節點，每個容器中的節點具有唯一的對象掌握它的擁有權(ownership)。對于這種容器的應用，優先隊列隻能删除最小節點，因為你根本無從知道它的其他節點是什麼。
但是優先隊列除了作為一種容器外還有另一個作用，就是可以找到最小節點。很多應用是針對這個功能的，它們并沒有将擁有權完全轉移給優先隊列，而是把優先隊列作為一個最小節點的選擇器，從一堆節點中依次将它們選出來。這樣一來節點的擁有權就可能同時被其他對象掌握。也就是說某個節點雖不是最小節點，不能從優先隊列那裡“已知”，但卻可以從其他的擁有者那裡“已知”。
這種優先隊列的應用也是很常見的。設想我們有一個鬧鐘，它可以記錄很多個響鈴時間，不過由于時間是線性的，鈴隻能一個個按先後次序響，優先隊列就很适合用來做這樣的挑選。另一方面使用者應該可以随時取消一個“已知”的響鈴時間，這就需要進行任意已知節點的删除操作了。
我們的這種删除操作需要指定被删除的節點，這和原來删除根節點的操作是相容的，因為根節點肯定是已知的。上面已經提過，在删除一個節點以後，将會剩下它的兩棵子樹，它們都是左偏樹，我們先通過p=merge(left(x)，right(x))把它們合并成一棵新的左偏樹。現在p指向了這棵新的左偏樹，如果我們删除的是根節點，此時任務已經完成了。不過，如果被删除節點x不是根節點就有點麻煩了。這時p指向的新樹的距離有可能比原來x的距離要大或小，這勢必有可能影響原來x的父節點q的距離，因為q現在成為新樹p的父節點了。于是就要仿照合并操作裡面的做法，對q的左右子樹作出調整，并更新q的距離。這一過程引起了連鎖反應，我們要順着q的父指針鍊一直往上進行調整(見圖1.6-9)。
新樹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的父節點也要做出同樣的處理。
https://yqfile.alicdn.com/a8cad28b49444d209629f7045ce16af2d07e2f43.png" >
剩下就是另外一種情況了，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的距離的情況，不符合左偏樹的性質1。不論哪種情況，删除操作都可以結束了。注意到，每一次循環，p的距離都會加1，而在循環體内，dist(p)+1最終将成為某個節點的距離。根據性質2，任何的距離都不會超過log2n，是以循環體的執行次數不會超過log2n。
情況2：p的距離增大了。在這種情況下，我們将必然一直從右子樹向上調整，直至q為空或p是q的左子樹時停止。一直從右子樹升上來這個事實說明了循環的次數不會超過log2n(性質2)。
最後我們看到這樣一個事實，這兩種情況隻會發生其中一種。如果某種情況的調整結束後，我們可以知道要麼q為空，要麼dist(p)+1=dist(q)。要麼p是q的左子樹。這三種情況都不會導緻另一情況發生。直覺上來講，如果合并後的新子樹導緻了父節點的一系列距離調整的話，要麼就一直是往小調整，要麼是一直往大調整，不會出現交替的情況。
我們已經知道合并出新子樹p的複雜度是o(log2n)，向上調整距離的複雜度也是o(log2n)，故删除操作的最壞情況的時間複雜度是o(log2n)。如果左偏樹非常傾斜，實際應用情況下要比這個快得多。
由左偏樹的各種操作可以看出，左偏樹作為可并堆的實作，它的各種操作性能都十分優秀，且程式設計複雜度比較低，可以說是一個“成本效益”十分高的資料結構。左偏樹之是以是很好的可并堆實作，是因為它能夠比較充分地利用堆中的有用資訊，沒有将這些資訊浪費掉。根據堆特征，我們知道，從根節點向下到任何一個外節點的路徑都是有序的。存在越長的路徑，說明樹的整體有序性越強，與平衡樹不同(平衡樹根本不允許有很長的路徑)，左偏樹盡大約一半的可能保留了這個長度，并将它甩向左側，利用它來縮短節點的距離以提高性能。這裡我們不進行嚴格的讨論。左偏樹作為一個例子大緻告訴我們：放棄已有的資訊意味着算法性能上的犧牲。由于有序表的插入操作是按逆序發生的，保留了自然的有序性，是以是一種最好的左偏樹；而平衡樹的插入操作是按正序發生的，完全放棄了自然的有序性，是以是一種最壞的左偏樹。圖1.6-10分别列出了這兩種“極端”的左偏樹。
這裡，需要聲明的是，可用于可并堆的優先隊列并非僅左偏樹一種，二項堆(binomial heap)和fibonacci堆(fibonacci heap)都是十分優秀的可并堆。表1.6-1列出這些可并堆的時空效率。
https://yqfile.alicdn.com/8318cd547d1914463ec2ae3c92563cb1983b4899.png" >
由上表可以看出，這四種可并堆各有所長。雖然，左偏樹在時間效率上不如二項堆和fibonacci堆，在空間效率上不如二叉堆，但從“魚與熊掌不可兼得”的角度看，這正是左偏樹可利用的價值所在。因為在很多情況下，時間複雜度、空間複雜度和程式設計複雜度之間是沖突的：fibonacci堆時間複雜度最低，但程式設計複雜度讓人無法接受；二叉堆的空間複雜度和程式設計複雜度都很低，但合并二叉堆的時間複雜度(o(n))卻是緻命弱點，用它來實作可并堆，則合并操作必然成為算法的瓶頸。左偏樹在存儲性質上，沒有二叉堆那樣的缺陷；作為二叉堆的一種替代品應用于各種優先隊列，很多時候甚至比二叉堆更友善。由此可見，左偏樹比較均衡地協調了時間複雜度、空間複雜度和程式設計複雜度之間的沖突。
1.6.3 應用左偏樹解題
若現實生活中的問題可轉化為合并兩個優先隊列的數學模型，則采用左偏樹解題是最為明智的選擇。我們不妨通過一個範例來體驗左偏樹的應用價值。
【1.6.1 financial fraud】
【問題描述】
bernard madoff是一位美國的股票經紀人、投資顧問、nasdaq股票市場的非執行董事長，并被認為是曆史上最大的龐氏(ponzi)騙局的操盤手。
兩個程式員jerome ohara和george perez，幫助bernard madoff編寫程式，産生虛假的記錄，因而被指控涉嫌僞造代理經銷商的記錄和變造投資顧問的記錄。
在這些年中每個季度，這兩個程式員都會收到一個資料表，給出在這一時期的一系列的利潤記錄a1 a2 … an。由于經濟危機，這些可怕的記錄可能會吓得投資者望而卻步。是以，這兩程式員被要求将這些記錄變造為b1 b2 … bn。為了欺騙投資者，任何一項記錄必定不能小于前面的記錄(也就是說，對任意的1≤i在另一方面，他們為他們的非法工作定義了一個冒險值(risk value)：risk value=a1-b1+a2-b2+…+an-bn。例如，原始的利潤記錄是300、400、200、100，如果他們選擇300、400、400、400作為虛假記錄，則冒險值是0+0+200+300=500。但如果他們選擇250、250、250、250作為虛假記錄，則冒險值是50+150+50+150=400。為了避免引起懷疑，他們需要最小化冒險值。
給出原始利潤記錄的一些拷貝，請你找出最小可能的冒險值。
輸入：
輸入有多個測試用例(至多20個)。
對每個測試用例，第一行給出一個整數n(1≤n≤50000)，下一行給出n個整數a1a2…an(-109≤ai≤109)。輸入以n=0結束。
輸出：
對每個測試用例，輸出一行，給出最小可能的冒險值。
試題解析
簡述題意：給出含n(≤50000)個數的序列a［1］…a［n］，求一個非遞減的序列b［1］…b［n］，使得∑ni=1a［i］-b［i］最小。
我們先來看看兩個最特殊的情況：
特殊情況1：a［1］≤a［2］≤…≤a［n］，在這種情況下，顯然最優解為b［i］=a［i］；
特殊情況2：a［1］≥a［2］≥…≥a［n］，這時，最優解為b［i］=x，其中x是數列a的中位數(為了友善讨論和程式實作，中位數都是指數列中第n/22」大的數)。
于是我們可以初步建立起這樣一個思路：把1…n劃分成m個區間，
［q［1］，q［2］-1］，［q［2］，q［3］-1］，…，［q［m］，q［m+1］-1］(q［i］為第i個區間的首指針，q［m+1］=n+1)
b序列中每個區間的元素值取a序列對應區間的中位數，即：
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］的中位數)
顯然，在上面第一種情況下m=n，q［i］=i；在第二種情況下m=1，q［1］=1。這樣的想法究竟對不對呢？應該怎樣實作？
若某序列前半部分a［1］，a［2］，…，a［n］的最優解為(u，u，…，u)，後半部分a［n+1］，a［n+2］，…，a［m］的最優解為(v，v，…，v)，那麼整個序列的最優解是什麼呢？若u≤v，顯然整個序列的最優解為(u，u，…，u，v，v，…，v)。否則，設整個序列的最優解為(b［1］，b［2］，…，b［m］)，則顯然b［n］≤u(否則我們把前半部分的解(b［1］，b［2］，…，b［n］)改為(u，u，…，u)，由題設知整個序列的解不會變壞)，同理b［n+1］≥v。接下來，我們将看到下面這個事實：
【定理1.6-2】 對于任意一個序列a［1］，a［2］，…，a［n］，如果最優解為(u，u，…，u)，那麼在滿足u≤u′≤b［1］或b［n］≤u′≤u的情況下，(b［1］，b［2］，…，b［n］)不會比(u′，u′，…，u′)更優。
證明：我們用歸納法證明u≤u′≤b［1］的情況，b［n］≤u′≤u的情況可以類似證明。
當n=1時，u=a［1］，命題顯然成立。
當n>1時，假設對于任意長度小于n的序列命題都成立，現在證明對于長度為n的序列命題也成立。首先把(b［1］，b［2］，…，b［n］)改為(b［1］，b［1］，…，b［1］)，這一改動将不會導緻解變壞，因為如果解變壞了，由歸納假設可知a［2］，a［3］，…，a［n］的中位數w>u，這樣的話，最優解就應該為(u，u，…，u，w，w，…，w)，沖突。然後我們再把(b［1］，b［1］，…，b［1］)改為(u′，u′，…，u′)，由于a［1］-x+a［2］-x+…+a［n］-x的幾何意義為數軸上點x到點a［1］，a［2］，…，a［n］的距離之和，且u≤u′≤b［1］，顯然點u′到各點的距離之和不會比點b［1］到各點的距離之和大，也就是說，(b［1］，b［2］，…，b［n］)不會比(v，v，…，v)更優。(證畢)
再回到之前的論述，由于b［n］≤u，作為上述事實的結論，我們可以得知，将(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］)，這樣并不會使解變壞。也就是說，整個序列的最優解為(b［n］，b［n］，…，b［n］，b［n+1］，b［n+1］，…，b［n+1］)。再考慮一下該解的幾何意義，設整個序列的中位數為w，則令b［n］=b［n+1］=w，将得到整個序列的最優解(w，w，…，w)。
分析到這裡，我們一開始的想法已經有了理論依據，算法也不難構思了：
延續我們一開始的思路：假設我們已經找到前k個數a［1］，a［2］，…，a［k］(kw［m+1］，我們需要将最後兩個區間合并，并找出新區間的最優解(也就是序列a中，下标在這個新區間内的各項的中位數)。重複這個合并過程，直至w［1］≤w［2］≤…≤w［m］時結束，然後繼續處理下一個數。
這個算法的正确性前面已經論證過了，現在我們需要考慮一下資料結構的選取。算法中涉及以下兩種操作：合并兩個有序集以及查詢某個有序集内的中位數。能較高效地支援這兩種操作的資料結構有不少，一個比較明顯的例子是二叉檢索樹(bst)，它的詢問操作複雜度是o(log2n)，但合并操作不甚理想，采用啟發式合并，總時間複雜度為o(nlog22n)。
有沒有更好的選擇呢？通過進一步分析，我們發現隻有當某一區間内的中位數比後一區間内的中位數大時，合并操作才會發生；也就是說，任一區間與後面的區間合并後，該區間内的中位數不會變大。于是我們可以用最大堆來維護每個區間内的中位數，當堆中的元素大于該區間内元素的一半時，删除堆頂元素，這樣堆中的元素始終為區間内較小的一半元素，堆頂元素即為該區間内的中位數。考慮到我們必須高效地完成合并操作，左偏樹是一個理想的選擇。雖然前面介紹的左偏樹是最小堆，但在本題中，顯然隻需把左偏樹的性質稍做修改，就可以實作最大堆了。左偏樹的詢問操作時間複雜度為o(1)，删除和合并操作時間複雜度都是o(log2n)，而詢問操作和合并操作少于n次，删除操作不超過n/2次(因為删除操作隻會在合并兩個元素個數為奇數的堆時發生)，是以用左偏樹實作，可以把算法的時間複雜度降為o(n*log2n)。
程式清單