算法合集之左偏樹的特點及其應用-文庫吧資料
2024-10-22 20:30本頁面
【正文】 一個整數(shù)序列 a1 , a2 , … , a n，求一個不下降序列 b1≤b2≤… ≤bn，使得數(shù)列 {ai} 和 {bi} 的各項之差的絕對值之和 |a1 b1| + |a2 b2| + … + |a n bn| 最小。 最右路徑 : 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é)點 – Decrease —— 減小一個節(jié)點的鍵值 Winter Camp 2021 演示稿 6 左偏樹的操作 —— 合并 ? 合并操作是遞歸進行的 a b a L1 R1 b L2 R2 T1 T2 merge 合并 T1和 T2兩棵左偏樹 a L1 merge b L2 R2 R1 先將 T1的右子樹與 T2合并 Winter Camp 2021 演示稿 7 左偏樹的操作 —— 合并 ? 合并操作是遞歸進行的 a L1 merge b L2 R2 R1 R’ 先將 T1的右子樹與 T2合并 ’Winter Camp 2021 演示稿 8 左偏樹的操作 —— 合并 ? 合并操作是遞歸進行的 a L1 R’ dist(R’ ) dist(L1) a L1 R’ 交換左右子樹并更新根節(jié)點距離 合并后的右子樹距離可能大于左子樹距離 Winter Camp 2021 演示稿 9 左偏樹的操作 —— 合并 ? 合并操作的代碼如下：
教學課件相關推薦
鄂ICP備17016276號-1