算法合集之左偏樹的特點及其應用-wenkub
2022-10-31 20:30:47 本頁面
【正文】 r Camp 2021 演示稿 25 例題：數(shù)字序列 —— 算法分析 ? 現(xiàn)在，我們需要 合并 、 取最大元素 和 刪除 三種操作，而這些都是可并堆的基本操作。 Winter Camp 2021 演示稿 27 總結(jié) ?左偏樹的特點： – 時空效率高 – 編程復雜度低 ?左偏樹的應用： – 可并堆 – 優(yōu)先隊列 性價比高 補充二叉堆的不足 Winter Camp 2021 演示稿 28 。 ? 二項堆和 Fibonacci堆某些操作比左偏樹快，但對于本題，三者的總時間復雜度均為 O(nlogn) ? 二項堆和 Fibonacci堆的空間需求比較大，編程實現(xiàn)也遠沒有左偏樹簡單。 b b1 b2 b3 b4 b5 b6 b7 b8 … … bk s1 s2 …… sm1 sm ak+1 加入 ak+1后，怎樣得到前 k+1項的最優(yōu)解？ 例題：數(shù)字序列 —— 算法分析 Winter Camp 2021 演示稿 23 ? 若 ak+1sm，直接令 sm+1＝ ak+1，得到前 k+1項的最優(yōu)解； ? 否則，將 ak+1并入第 m個區(qū)間，并更新 sm ? 不斷 檢查最后兩個區(qū)間的解 sm1和 sm，若 sm1≥sm， 合并最后兩個區(qū)間，并令新區(qū)間的解為該區(qū)間內(nèi)的中位數(shù)。 最右路徑 : A－ C－ G 最右路徑節(jié)點數(shù) = 3 距離 = 2 8個節(jié)點的左偏樹的最大距離： ?log(8+1)? 1 = 2 A B D 0 0 0 1 2 E H F 0 G 0 1 C 最右路徑長度即為左偏樹的距離 Winter Camp 2021 演示稿 5 左偏樹的操作 ? 左偏樹支持下面這些操作： – MakeNull —— 初始化一棵空的左偏樹 – Merge —— 合并兩棵左偏樹 – Insert —— 插入一個新節(jié)點 – Min —— 取得最小節(jié)點 – DeleteMin —— 刪除最小節(jié)點 – Delete —— 刪除任意已知節(jié)點 – Decr
教學課件相關推薦
鄂ICP備17016276號-1