【正文】 (Mergeable Heap) ，它除了支持優(yōu)先隊(duì)列的三個(gè)基本操作（插入，刪除，取最小節(jié)點(diǎn)），還支持一個(gè)很特殊的操作 ——合并操作。 ? 下表列出了幾種可并堆相應(yīng)操作的時(shí)間復(fù)雜度 操作 二叉堆 左偏樹 二項(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次，刪除操作不超過 n/2 次 ? 由于合并次數(shù)比較多，二叉堆的合并操作太慢了，總時(shí)間復(fù)雜度也無法令人滿意。 Winter Camp 2021 演示稿 4 左偏樹的性質(zhì) ? 定理：若一棵左偏樹有 N個(gè)節(jié)點(diǎn)，則該左偏樹的距離不超過 ?log(N+1)? 1。 最右路徑 : A－ C－ G 最右路徑節(jié)點(diǎn)數(shù) = 3 距離 = 2 8個(gè)節(jié)點(diǎn)的左偏樹的最大距離： ?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 —— 插入一個(gè)新節(jié)點(diǎn) – Min —— 取得最小節(jié)點(diǎn) – DeleteMin —— 刪除最小節(jié)點(diǎn) – Delete —— 刪除任意已知節(jié)點(diǎn) – Decrease —— 減小一個(gè)節(jié)點(diǎn)的鍵值 Winter Camp 2021 演示稿 6 左偏樹的操作 —— 合并 ? 合并操作是遞歸進(jìn)行的 a b a L1 R1 b L2 R2 T1 T2 merge 合并 T1和 T2兩棵左偏樹 a L1 merge b L2