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

左偏樹的特點(diǎn)及其應(yīng)用 廣東省中山市第一中學(xué)黃源河 2 左偏樹的定義 左偏樹 LeftistTree 是一種可并堆 MergeableHeap 它除了支持優(yōu)先隊(duì)列的三個(gè)基本操作 插入 刪除 取最小節(jié)點(diǎn) 還支持一個(gè)很特殊的操作 合并操作 左偏樹是一棵堆有序 HeapOrdered 二叉樹 左偏樹滿足左偏性質(zhì) LeftistProperty 3 左偏樹的定義 左偏性質(zhì) 定義一棵左偏樹中的外節(jié)點(diǎn) ExternalNode 為左子樹或右子樹為空的節(jié)點(diǎn) 定義節(jié)點(diǎn)i的距離 dist i 為節(jié)點(diǎn)i到它的后代中 最近的外節(jié)點(diǎn)所經(jīng)過的邊數(shù) 任意節(jié)點(diǎn)的左子節(jié)點(diǎn)的距離不小于右子節(jié)點(diǎn)的距離 左偏性質(zhì) 由左偏性質(zhì)可知 一個(gè)節(jié)點(diǎn)的距離等于以該節(jié)點(diǎn)為根的子樹最右路徑的長(zhǎng)度 4 左偏樹的性質(zhì) 定理 若一棵左偏樹有N個(gè)節(jié)點(diǎn) 則該左偏樹的距離不超過 log N 1 1 最右路徑 A C G最右路徑節(jié)點(diǎn)數(shù) 3距離 2 8個(gè)節(jié)點(diǎn)的左偏樹的最大距離 log 8 1 1 2 5 左偏樹的操作 左偏樹支持下面這些操作 MakeNull 初始化一棵空的左偏樹Merge 合并兩棵左偏樹Insert 插入一個(gè)新節(jié)點(diǎn)Min 取得最小節(jié)點(diǎn)DeleteMin 刪除最小節(jié)點(diǎn)Delete 刪除任意已知節(jié)點(diǎn)Decrease 減小一個(gè)節(jié)點(diǎn)的鍵值 6 左偏樹的操作 合并 合并操作是遞歸進(jìn)行的 合并T1和T2兩棵左偏樹 先將T1的右子樹與T2合并 7 左偏樹的操作 合并 合并操作是遞歸進(jìn)行的 a L1 R 先將T1的右子樹與T2合并 8 左偏樹的操作 合并 合并操作是遞歸進(jìn)行的 交換左右子樹并更新根節(jié)點(diǎn)距離 合并后的右子樹距離可能大于左子樹距離 9 左偏樹的操作 合并 合并操作的代碼如下 FunctionMerge A B IfA NULLThenreturnBIfB NULLThenreturnAIfkey B dist left A Thenswap left A right A Ifright A NULLThendist A 0Elsedist A dist right A 1returnAEndFunction 10 左偏樹的操作 合并 下面是一個(gè)合并的例子 11 左偏樹的操作 合并 下面是一個(gè)合并的例子 12 左偏樹的操作 合并 下面是一個(gè)合并的例子 13 左偏樹的操作 合并 下面是一個(gè)合并的例子 18 NULL 14 左偏樹的操作 合并 下面是一個(gè)合并的例子 37 7 0 1 15 左偏樹的操作 合并 下面是一個(gè)合并的例子 1 1 2 26 17 37 18 8 7 16 左偏樹的操作 合并 下面是一個(gè)合并的例子 0 2 17 左偏樹的操作 合并 下面是一個(gè)合并的例子 3 10 2 0 1 18 左偏樹的操作 合并 合并操作都是一直沿著兩棵左偏樹的最右路徑進(jìn)行的 一棵N個(gè)節(jié)點(diǎn)的左偏樹 最右路徑上最多有 log N 1 個(gè)節(jié)點(diǎn) 因此 合并操作的時(shí)間復(fù)雜度為 O logN1 logN2 O logN 19 左偏樹的操作 插入 插入一個(gè)新節(jié)點(diǎn)把待插入節(jié)點(diǎn)作為一棵單節(jié)點(diǎn)左偏樹合并兩棵左偏樹時(shí)間復(fù)雜度 O logN 20 左偏樹的操作 刪除 刪除最小節(jié)點(diǎn)刪除根節(jié)點(diǎn)合并左右子樹時(shí)間復(fù)雜度 O logN 21 例題 數(shù)字序列 給定一個(gè)整數(shù)序列a1 a2 an 求一個(gè)不下降序列b1 b2 bn 使得數(shù)列 ai 和 bi 的各項(xiàng)之差的絕對(duì)值之和 a1 b1 a2 b2 an bn 最小 數(shù)據(jù)規(guī)模 1 n 106 0 ai 2 109 22 假設(shè)數(shù)列a1 a2 ak的最優(yōu)解為b1 b2 bk合并 bi 中相同的項(xiàng) 得到m個(gè)區(qū)間和數(shù)列s1 s2 sm顯然 si為數(shù)列a中 下標(biāo)在第i個(gè)區(qū)間內(nèi)的各項(xiàng)的中位數(shù) b ak 1 加入ak 1后 怎樣得到前k 1項(xiàng)的最優(yōu)解 例題 數(shù)字序列 算法分析 23 若ak 1 sm 直接令sm 1 ak 1 得到前k 1項(xiàng)的最優(yōu)解 否則 將ak 1并入第m個(gè)區(qū)間 并更新sm不斷檢查最后兩個(gè)區(qū)間的解sm 1和sm 若sm 1 sm 合并最后兩個(gè)區(qū)間 并令新區(qū)間的解為該區(qū)間內(nèi)的中位數(shù) b ak 1 s m s m 1 例題 數(shù)字序列 算法分析 24 下面考慮數(shù)據(jù)結(jié)構(gòu)的選取我們需要維護(hù)若干個(gè)有序集 并能夠高效完成下面兩個(gè)操作 合并兩個(gè)有序集查詢某個(gè)有序集的中位數(shù)進(jìn)一步分析 加入一個(gè)元素后 發(fā)生一連串合并操作 合并后有序集的中位數(shù)不會(huì)比原來大因此 每個(gè)有序集內(nèi)只保存較小的一半元素 查詢中位數(shù)操作轉(zhuǎn)化為取最大元素操作 例題 數(shù)字序列 算法分析 25 例題 數(shù)字序列 算法分析 現(xiàn)在 我們需要合并 取最大元素和刪除三種操作 而這些都是可并堆的基本操作 下表列出了幾種可并堆相應(yīng)操作的時(shí)間復(fù)雜度 26 例題 數(shù)字序列 算法分析 在本題中 合并操作和取最大元素操作少于n次 刪除操作不超過n 2次由于合并次數(shù)比較多 二叉堆的合并操作太慢了 總時(shí)間復(fù)雜度也無法令人滿意 二項(xiàng)堆和Fibonacci堆某些操作比左偏樹快 但對(duì)于本題 三者的總時(shí)間復(fù)雜度均為O nlogn 二項(xiàng)堆和Fibonacci堆的空間需求比較大 編程實(shí)現(xiàn)也遠(yuǎn)沒