算法合集之左偏樹的特點及其應(yīng)用(參考版)
2024-10-19 20:30本頁面
【正文】 Winter Camp 2021 演示稿 27 總結(jié) ?左偏樹的特點： – 時空效率高 – 編程復(fù)雜度低 ?左偏樹的應(yīng)用： – 可并堆 – 優(yōu)先隊列 性價比高 補充二叉堆的不足 Winter Camp 2021 演示稿 28 。 ? 二項堆和 Fibonacci堆某些操作比左偏樹快，但對于本題，三者的總時間復(fù)雜度均為 O(nlogn) ? 二項堆和 Fibonacci堆的空間需求比較大，編程實現(xiàn)也遠沒有左偏樹簡單。 例題：數(shù)字序列 —— 算法分析 Winter Camp 2021 演示稿 25 例題：數(shù)字序列 —— 算法分析 ? 現(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ù)。 ?因此，合并操作的時間復(fù)雜度為： O(log N1 + log N2) = O(log N) Winter Camp 2021 演示稿 19 左偏樹的操作 —— 插入 ?插入一個新節(jié)點 – 把待插入節(jié)點作為一棵單節(jié)點左偏樹 – 合并兩棵左偏樹 – 時間復(fù)雜度： O(log N) Merge Winter Camp 2021 演示稿 20 左偏樹的操作 —— 刪除 ?刪除最小節(jié)點 – 刪除根節(jié)點 – 合并左右子樹 – 時間復(fù)雜度： O(log N) Merge Winter Camp 2021 演示稿 21 例題：數(shù)字序列 ?給定
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1