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