算法合集之左偏樹的特點及其應(yīng)用-ppt課件

1、Winter Camp 2005 演示稿左偏樹的定義l左偏樹左偏樹(Leftist Tree)是一種可并堆是一種可并堆(Mergeable Heap) ，它除了支持優(yōu)先隊列的三個基本操作，它除了支持優(yōu)先隊列的三個基本操作插入，刪除，取最小節(jié)點），還支持一個很插入，刪除，取最小節(jié)點），還支持一個很特殊的操作特殊的操作合并操作。合并操作。l左偏樹是一棵堆有序左偏樹是一棵堆有序(Heap Ordered)二叉樹。二叉樹。l左偏樹滿足左偏性質(zhì)左偏樹滿足左偏性質(zhì)(Leftist Property)。Winter Camp 2005 演示稿左偏樹的定義 左偏性質(zhì)l定義一棵左偏樹中的外節(jié)點(External

2、 Node) 為左子樹或右子樹為空的節(jié)點。l定義節(jié)點 i 的距離(dist(i) 為節(jié)點 i 到它的后代中，最近的外節(jié)點所經(jīng)過的邊數(shù)。l任意節(jié)點的左子節(jié)點的距離不小于右子節(jié)點的距離左偏性質(zhì)）。 l由左偏性質(zhì)可知，一個節(jié)點的距離等于以該節(jié)點為根的子樹最右路徑的長度。Winter Camp 2005 演示稿左偏樹的性質(zhì)l定理：若一棵左偏樹有N個節(jié)點，則該左偏樹的距離不超過 log(N+1) -1。最右路徑: ACG最右路徑節(jié)點數(shù) = 3間隔 = 28個節(jié)點的左偏樹的最大距離：log(8+1) -1 = 2ABD00012EHF 0G 01C最右路徑長度即為左偏樹的距離Winter Camp 200

3、5 演示稿左偏樹的操作l左偏樹支持下面這些操作：lMakeNull 初始化一棵空的左偏樹lMerge 合并兩棵左偏樹lInsert 插入一個新節(jié)點lMin 取得最小節(jié)點lDeleteMin 刪除最小節(jié)點lDelete 刪除任意已知節(jié)點lDecrease 減小一個節(jié)點的鍵值Winter Camp 2005 演示稿左偏樹的操作 合并l合并操作是遞歸進(jìn)行的a dist(L1)aL1R交換左右子樹并更新根節(jié)點距離合并后的右子樹距離可能大于左子樹距離Winter Camp 2005 演示稿左偏樹的操作 合并l合并操作的代碼如下：lFunction Merge(A, B)lIf A = NULL Then

4、 return BlIf B = NULL Then return AlIf key(B) dist(left(A) Thenlswap(left(A), right(A)lIf right(A) = NULL Then dist(A) 0lElse dist(A) dist(right(A) + 1lreturn AlEnd FunctionWinter Camp 2005 演示稿左偏樹的操作 合并l下面是一個合并的例子：61218243718700120013108261711000Merge (3, 6)Winter Camp 2005 演示稿左偏樹的操作 合并l下面是一個合并的例子：6

5、1218243718782617Merge (8, 6)Merge (3, 6)Winter Camp 2005 演示稿左偏樹的操作 合并l下面是一個合并的例子：3718782617Merge (8, 7)Merge (8, 6)Merge (3, 6)Winter Camp 2005 演示稿左偏樹的操作 合并l下面是一個合并的例子：18Merge (8,18)Merge (8, 7)Merge (8, 6)Merge (3, 6)NULL82617Winter Camp 2005 演示稿左偏樹的操作 合并l下面是一個合并的例子：Merge (8, 7)Merge (8, 6)Merge (3

6、, 6)188261737701?Winter Camp 2005 演示稿左偏樹的操作 合并l下面是一個合并的例子：Merge (8, 6)Merge (3, 6)11226173718861218247Winter Camp 2005 演示稿左偏樹的操作 合并l下面是一個合并的例子：Merge (3, 6)02?26177371886121824310Winter Camp 2005 演示稿左偏樹的操作 合并l下面是一個合并的例子：Merge (3, 6)26177371886121824310201Winter Camp 2005 演示稿左偏樹的操作 合并l合并操作都是一直沿著兩棵左偏樹的

7、最右路徑進(jìn)行的。l一棵N個節(jié)點的左偏樹，最右路徑上最多有 log(N+1) 個節(jié)點。l因此，合并操作的時間復(fù)雜度為：O(log N1 + log N2) = O(log N)Winter Camp 2005 演示稿左偏樹的操作 插入l插入一個新節(jié)點l把待插入節(jié)點作為一棵單節(jié)點左偏樹l合并兩棵左偏樹l時間復(fù)雜度：O(log N)MergeWinter Camp 2005 演示稿左偏樹的操作 刪除l刪除最小節(jié)點l刪除根節(jié)點l合并左右子樹l時間復(fù)雜度：O(log N)MergeWinter Camp 2005 演示稿例題：數(shù)字序列l(wèi)給定一個整數(shù)序列 a1 , a2 , , an，求一個不下降序列 b

8、1b2bn，使得數(shù)列 ai 和 bi 的各項之差的絕對值之和 |a1 - b1| + |a2 - b2| + + |an - bn| 最小。l數(shù)據(jù)規(guī)模：1n106, 0ai2*109 Winter Camp 2005 演示稿l假設(shè)數(shù)列 a1,a2, ,ak 的最優(yōu)解為 b1,b2, ,bkl合并 bi 中相同的項，得到 m 個區(qū)間和數(shù)列 s1,s2, ,sml顯然，si 為數(shù)列 a 中，下標(biāo)在第 i 個區(qū)間內(nèi)的各項的中位數(shù)。bb1 b2 b3 b4 b5 b6 b7 b8 bk s1 s2 sm-1 smak+1加入ak+1后，怎樣得到前k+1項的最優(yōu)解？例題：數(shù)字序列 算法分析Winter

9、Camp 2005 演示稿l若ak+1sm，直接令sm+1ak+1，得到前k+1項的最優(yōu)解；l否則，將ak+1并入第m個區(qū)間，并更新sml不斷 檢查最后兩個區(qū)間的解 sm-1和 sm，假設(shè)sm-1sm，合并最后兩個區(qū)間，并令新區(qū)間的解為該區(qū)間內(nèi)的中位數(shù)。b s1 s2 sm-1 smak+1smsm-1例題：數(shù)字序列 算法分析Winter Camp 2005 演示稿l下面考慮數(shù)據(jù)結(jié)構(gòu)的選取l我們需要維護(hù)若干個有序集，并能夠高效完成下面兩個操作：l合并兩個有序集l查詢某個有序集的中位數(shù)l進(jìn)一步分析，加入一個元素后，發(fā)生一連串合并操作，合并后有序集的中位數(shù)不會比原來大l因此，每個有序集內(nèi)只保存較小

10、的一半元素，查詢中位數(shù)操作轉(zhuǎn)化為取最大元素操作。例題：數(shù)字序列 算法分析Winter Camp 2005 演示稿例題：數(shù)字序列 算法分析l如今，我們需要合并、取最大元素和刪除三種操作，而這些都是可并堆的基本操作。l下表列出了幾種可并堆相應(yīng)操作的時間復(fù)雜度Winter Camp 2005 演示稿例題：數(shù)字序列 算法分析l在本題中，合并操作和取最大元素操作少于 n次，刪除操作不超過 n/2 次l由于合并次數(shù)比較多，二叉堆的合并操作太慢了，總時間復(fù)雜度也無法令人滿意。l二項堆和Fibonacci堆某些操作比左偏樹快，但對于本題，三者的總時間復(fù)雜度均為O(nlogn)l二項堆和Fibonacci堆的空間需求比較大，編程實現(xiàn)也