算法合集之左偏樹的特點及其應用-wenkub.com
2024-10-13 20:30 本頁面
【正文】 ? 相比之下，本題用左偏樹實現(xiàn)，時空復雜度都可以接受，編程實現(xiàn)也非常簡單，是十分理想的選擇。 b s1 s2 …… sm1 sm ak+1 ’ m s’ m1 例題：數(shù)字序列 —— 算法分析 Winter Camp 2021 演示稿 24 ? 下面考慮數(shù)據(jù)結構的選取 ? 我們需要維護若干個有序集，并能夠高效完成下面兩個操作： – 合并兩個有序集 – 查詢某個有序集的中位數(shù) ? 進一步分析，加入一個元素后，發(fā)生一連串合并操作，合并后有序集的中位數(shù)不會比原來大 ? 因此，每個有序集內只保存較小的一半元素，查詢中位數(shù)操作轉化為取最大元素操作。 ?一棵 N個節(jié)點的左偏樹，最右路徑上最多有 ?log(N+1)? 個節(jié)點。 ? 任意節(jié)點的左子節(jié)點的距離不小于右子節(jié)點的距離（左偏性質）。 ? 左偏樹是一棵 堆有序 (Heap Ordered)二叉樹。 ? 左偏樹滿足 左偏性質 (Leftist Property)。 ? 由左偏性質可知，一個節(jié)點的距離等于以該節(jié)點為根的子樹最右路徑的長度。 ?因此，合并操作的時間復雜度為： O(log N1 + log N2) = O(log N) Winter Camp 2021 演示稿 19 左偏樹的操作 —— 插入 ?插入一個新節(jié)點 – 把待插入節(jié)點作為一棵單節(jié)點左偏樹 – 合并兩棵左偏樹 – 時間復雜度： O(log N) Merge Winter Camp 2021 演示稿 20 左偏樹的操作 —— 刪除 ?刪除最小節(jié)點 – 刪除根節(jié)點 – 合并左右子樹 – 時間復雜度： O(log N) Merge Winter Camp 2021 演示稿 21 例題：數(shù)字序列 ?給定一個整數(shù)序列 a1 , a2 , … , a n，求一個不下降序列 b1≤b2≤… ≤bn，使得數(shù)列 {ai} 和 {bi} 的各項之差的絕對值之和 |a1 b1| + |a2 b2| + … + |a n bn| 最小。 例題：數(shù)字序列 —— 算法分析 Winte
教學課件相關推薦
鄂ICP備17016276號-1