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

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

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

3、5 演示稿左偏樹的操作l左偏樹支持下面這些操作：lMakeNull 初始化一棵空的左偏樹lMerge 合并兩棵左偏樹lInsert 插入一個(gè)新節(jié)點(diǎn)lMin 取得最小節(jié)點(diǎn)lDeleteMin 刪除最小節(jié)點(diǎn)lDelete 刪除任意已知節(jié)點(diǎn)lDecrease 減小一個(gè)節(jié)點(diǎn)的鍵值Winter Camp 2005 演示稿左偏樹的操作 合并l合并操作是遞歸進(jìn)行的a dist(L1)aL1R交換左右子樹并更新根節(jié)點(diǎn)距離合并后的右子樹距離可能大于左子樹距離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下面是一個(gè)合并的例子：61218243718700120013108261711000Merge (3, 6)Winter Camp 2005 演示稿左偏樹的操作 合并l下面是一個(gè)合并的例子：6

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

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

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

8、1b2bn，使得數(shù)列 ai 和 bi 的各項(xiàng)之差的絕對(duì)值之和 |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 中相同的項(xiàng)，得到 m 個(gè)區(qū)間和數(shù)列 s1,s2, ,sml顯然，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ù)字序列 算法分析Winter

9、Camp 2005 演示稿l若ak+1sm，直接令sm+1ak+1，得到前k+1項(xiàng)的最優(yōu)解；l否則，將ak+1并入第m個(gè)區(qū)間，并更新sml不斷 檢查最后兩個(gè)區(qū)間的解 sm-1和 sm，假設(shè)sm-1sm，合并最后兩個(gè)區(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ù)若干個(gè)有序集，并能夠高效完成下面兩個(gè)操作：l合并兩個(gè)有序集l查詢某個(gè)有序集的中位數(shù)l進(jìn)一步分析，加入一個(gè)元素后，發(fā)生一連串合并操作，合并后有序集的中位數(shù)不會(huì)比原來大l因此，每個(gè)有序集內(nèi)只保存較小

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