算法合集之左偏樹(shù)的特點(diǎn)及其應(yīng)用-資料下載頁(yè)
2024-10-16 20:30本頁(yè)面
【正文】 s2 …… sm1 sm ak+1 ’ m s’ m1 例題：數(shù)字序列 —— 算法分析 Winter Camp 2021 演示稿 24 ? 下面考慮數(shù)據(jù)結(jié)構(gòu)的選取 ? 我們需要維護(hù)若干個(gè)有序集，并能夠高效完成下面兩個(gè)操作： – 合并兩個(gè)有序集 – 查詢某個(gè)有序集的中位數(shù) ? 進(jìn)一步分析，加入一個(gè)元素后，發(fā)生一連串合并操作，合并后有序集的中位數(shù)不會(huì)比原來(lái)大 ? 因此，每個(gè)有序集內(nèi)只保存較小的一半元素，查詢中位數(shù)操作轉(zhuǎn)化為取最大元素操作。 例題：數(shù)字序列 —— 算法分析 Winter Camp 2021 演示稿 25 例題：數(shù)字序列 —— 算法分析 ? 現(xiàn)在，我們需要 合并 、 取最大元素 和 刪除 三種操作，而這些都是可并堆的基本操作。 ? 下表列出了幾種可并堆相應(yīng)操作的時(shí)間復(fù)雜度 操作 二叉堆 左偏樹(shù) 二項(xiàng)堆 Fibonacci堆 取最小節(jié)點(diǎn) O(1) O(1) O(1) O(1) 插入 O(log N) O(log N) O(1) O(1) 刪除最小節(jié)點(diǎn) O(log N) O(log N) O(log N) O(log N) 合并 O(N) O(log N) O(log N) O(1) Winter Camp 2021 演示稿 26 例題：數(shù)字序列 —— 算法分析 ? 在本題中，合并操作和取最大元素操作少于 n次，刪除操作不超過(guò) n/2 次 ? 由于合并次數(shù)比較多，二叉堆的合并操作太慢了，總時(shí)間復(fù)雜度也無(wú)法令人滿意。 ? 二項(xiàng)堆和 Fibonacci堆某些操作比左偏樹(shù)快，但對(duì)于本題，三者的總時(shí)間復(fù)雜度均為 O(nlogn) ? 二項(xiàng)堆和 Fibonacci堆的空間需求比較大，編程實(shí)現(xiàn)也遠(yuǎn)沒(méi)有左偏樹(shù)簡(jiǎn)單。 ? 相比之下，本題用左偏樹(shù)實(shí)現(xiàn)，時(shí)空復(fù)雜度都可以接受，編程實(shí)現(xiàn)也非常簡(jiǎn)單，是十分理想的選擇。 Winter Camp 2021 演示稿 27 總結(jié) ?左偏樹(shù)的特點(diǎn)： – 時(shí)空效率高 – 編程復(fù)雜度低 ?左偏樹(shù)的應(yīng)用： – 可并堆 – 優(yōu)先隊(duì)列 性價(jià)比高 補(bǔ)充二叉堆的不足 Winter Camp 2021 演示稿 28
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1