1、左偏樹(shù)的特點(diǎn)及其應(yīng)用廣東省中山市第一中學(xué) 黃源河2左偏樹(shù)的定義左偏樹(shù)(Leftist Tree)是一種可并堆(Mergeable Heap) ，它除了支持優(yōu)先隊(duì)列的三個(gè)基本操作（插入，刪除，取最小節(jié)點(diǎn)），還支持一個(gè)很特殊的操作合并操作。左偏樹(shù)是一棵堆有序(Heap Ordered)二叉樹(shù)。左偏樹(shù)滿足左偏性質(zhì)(Leftist Property)。3左偏樹(shù)的定義 左偏性質(zhì)定義一棵左偏樹(shù)中的外節(jié)點(diǎn)(External Node) 為左子樹(shù)或右子樹(shù)為空的節(jié)點(diǎn)。定義節(jié)點(diǎn) i 的距離(dist(i) 為節(jié)點(diǎn) i 到它的后代中，最近的外節(jié)點(diǎn)所經(jīng)過(guò)的邊數(shù)。任意節(jié)點(diǎn)的左子節(jié)點(diǎn)的距離不小于右子節(jié)點(diǎn)的距離（左偏性質(zhì)）

2、。 由左偏性質(zhì)可知，一個(gè)節(jié)點(diǎn)的距離等于以該節(jié)點(diǎn)為根的子樹(shù)最右路徑的長(zhǎng)度。4左偏樹(shù)的性質(zhì)定理：若一棵左偏樹(shù)有N個(gè)節(jié)點(diǎn)，則該左偏樹(shù)的距離不超過(guò) log(N+1) -1。最右路徑: ACG最右路徑節(jié)點(diǎn)數(shù) = 3距離 = 28個(gè)節(jié)點(diǎn)的左偏樹(shù)的最大距離：log(8+1) -1 = 2ABD00012EHF0G01C最右路徑長(zhǎng)度即為左偏樹(shù)的距離5左偏樹(shù)的操作左偏樹(shù)支持下面這些操作：MakeNull 初始化一棵空的左偏樹(shù)Merge 合并兩棵左偏樹(shù)Insert 插入一個(gè)新節(jié)點(diǎn)Min 取得最小節(jié)點(diǎn)DeleteMin 刪除最小節(jié)點(diǎn)Delete 刪除任意已知節(jié)點(diǎn)Decrease 減小一個(gè)節(jié)點(diǎn)的鍵值6左偏樹(shù)的操作 合

3、并合并操作是遞歸進(jìn)行的a dist(L1)aL1R交換左右子樹(shù)并更新根節(jié)點(diǎn)距離合并后的右子樹(shù)距離可能大于左子樹(shù)距離9左偏樹(shù)的操作 合并合并操作的代碼如下：Function Merge(A, B)If A = NULL Then return BIf B = NULL Then return AIf key(B) dist(left(A) Thenswap(left(A), right(A)If right(A) = NULL Then dist(A) 0Else dist(A) dist(right(A) + 1return AEnd Function10左偏樹(shù)的操作 合并下面是一個(gè)合并的例子

4、：61218243718700120013108261711000Merge (3, 6)11左偏樹(shù)的操作 合并下面是一個(gè)合并的例子：61218243718782617Merge (8, 6)Merge (3, 6)12左偏樹(shù)的操作 合并下面是一個(gè)合并的例子：3718782617Merge (8, 7)Merge (8, 6)Merge (3, 6)13左偏樹(shù)的操作 合并下面是一個(gè)合并的例子：18Merge (8,18)Merge (8, 7)Merge (8, 6)Merge (3, 6)NULL8261714左偏樹(shù)的操作 合并下面是一個(gè)合并的例子：Merge (8, 7)Merge (8,

5、 6)Merge (3, 6)188261737701?15左偏樹(shù)的操作 合并下面是一個(gè)合并的例子：Merge (8, 6)Merge (3, 6)1122617371886121824716左偏樹(shù)的操作 合并下面是一個(gè)合并的例子：Merge (3, 6)02?2617737188612182431017左偏樹(shù)的操作 合并下面是一個(gè)合并的例子：Merge (3, 6)2617737188612182431020118左偏樹(shù)的操作 合并合并操作都是一直沿著兩棵左偏樹(shù)的最右路徑進(jìn)行的。一棵N個(gè)節(jié)點(diǎn)的左偏樹(shù)，最右路徑上最多有 log(N+1) 個(gè)節(jié)點(diǎn)。因此，合并操作的時(shí)間復(fù)雜度為：O(log N1

6、+ log N2) = O(log N)19左偏樹(shù)的操作 插入插入一個(gè)新節(jié)點(diǎn)把待插入節(jié)點(diǎn)作為一棵單節(jié)點(diǎn)左偏樹(shù)合并兩棵左偏樹(shù)時(shí)間復(fù)雜度：O(log N)Merge20左偏樹(shù)的操作 刪除刪除最小節(jié)點(diǎn)刪除根節(jié)點(diǎn)合并左右子樹(shù)時(shí)間復(fù)雜度：O(log N)Merge21例題：數(shù)字序列給定一個(gè)整數(shù)序列 a1 , a2 , , an，求一個(gè)不下降序列 b1b2bn，使得數(shù)列 ai 和 bi 的各項(xiàng)之差的絕對(duì)值之和 |a1 - b1| + |a2 - b2| + + |an - bn| 最小。數(shù)據(jù)規(guī)模：1n106, 0ai2*109 22假設(shè)數(shù)列 a1,a2, ,ak 的最優(yōu)解為 b1,b2, ,bk合并 bi

7、 中相同的項(xiàng)，得到 m 個(gè)區(qū)間和數(shù)列 s1,s2, ,sm顯然，si 為數(shù)列 a 中，下標(biāo)在第 i 個(gè)區(qū)間內(nèi)的各項(xiàng)的中位數(shù)。bb1 b2 b3 b4 b5 b6 b7 b8 bk s1 s2 sm-1 smak+1加入ak+1后，怎樣得到前k+1項(xiàng)的最優(yōu)解？例題：數(shù)字序列 算法分析23若ak+1sm，直接令sm+1ak+1，得到前k+1項(xiàng)的最優(yōu)解；否則，將ak+1并入第m個(gè)區(qū)間，并更新sm不斷 檢查最后兩個(gè)區(qū)間的解 sm-1和 sm，若sm-1sm，合并最后兩個(gè)區(qū)間，并令新區(qū)間的解為該區(qū)間內(nèi)的中位數(shù)。b s1 s2 sm-1 smak+1smsm-1例題：數(shù)字序列 算法分析24下面考慮數(shù)據(jù)結(jié)構(gòu)

8、的選取我們需要維護(hù)若干個(gè)有序集，并能夠高效完成下面兩個(gè)操作：合并兩個(gè)有序集查詢某個(gè)有序集的中位數(shù)進(jìn)一步分析，加入一個(gè)元素后，發(fā)生一連串合并操作，合并后有序集的中位數(shù)不會(huì)比原來(lái)大因此，每個(gè)有序集內(nèi)只保存較小的一半元素，查詢中位數(shù)操作轉(zhuǎn)化為取最大元素操作。例題：數(shù)字序列 算法分析25例題：數(shù)字序列 算法分析現(xiàn)在，我們需要合并、取最大元素和刪除三種操作，而這些都是可并堆的基本操作。下表列出了幾種可并堆相應(yīng)操作的時(shí)間復(fù)雜度操作二叉堆左偏樹(shù)二項(xiàng)堆Fibonacci堆取最小節(jié)點(diǎn)O(1)O(1)O(1)O(1)插入O(log N)O(log N)O(1)O(1)刪除最小節(jié)點(diǎn)O(log N)O(log N)O(log N)O(log N)合并O(N)O(log N)O(log N)O(1)26例題：數(shù)字序列 算法分析在本題中，合并操作和取最大元素操作少于 n次，刪除操作不超過(guò) n/2 次由于合并次數(shù)比較多，二叉堆的合并操作太慢了，總時(shí)間復(fù)雜度也無(wú)法令人滿意。二項(xiàng)堆和Fibonacci堆某些操作比左偏樹(shù)快，但對(duì)于本題，三者的總時(shí)間復(fù)雜度均為O(nlogn)