左偏堆的特點及其應(yīng)用推薦課件

1、2021/8/221Winter Camp 2005 演示稿2021/8/222左偏樹的定義l左偏樹左偏樹(Leftist Tree)是一種可并堆可并堆(Mergeable Heap) ，它除了支持優(yōu)先隊列的三個基本操作（插入，刪除，取最小節(jié)點），還支持一個很特殊的操作合并操作。l左偏樹是一棵堆有序堆有序(Heap Ordered)二叉樹。l左偏樹滿足左偏性質(zhì)左偏性質(zhì)(Leftist Property)。Winter Camp 2005 演示稿2021/8/223左偏樹的定義 左偏性質(zhì)l定義一棵左偏樹中的外節(jié)點外節(jié)點(External Node) 為左子樹或右子樹為空的節(jié)點。l定義節(jié)點 i 的

2、距離距離(dist(i) 為節(jié)點 i 到它的后代中，最近的外節(jié)點所經(jīng)過的邊數(shù)。l任意節(jié)點的左子節(jié)點的距離不小于右子節(jié)點的距離（左偏性質(zhì)）。 l由左偏性質(zhì)可知，一個節(jié)點的距離等于以該節(jié)點為根的子樹最右路徑的長度。Winter Camp 2005 演示稿2021/8/224左偏樹的性質(zhì)l定理：若一棵左偏樹有N個節(jié)點，則該左偏樹的距離不超過 log(N+1) -1。最右路徑: ACG最右路徑節(jié)點數(shù) = 3距離 = 28個節(jié)點的左偏樹的最大距離：log(8+1) -1 = 2ABD00012EHF 0G 01C最右路徑長度即為左偏樹的距離Winter Camp 2005 演示稿2021/8/225左偏

3、樹的操作l左偏樹支持下面這些操作：MakeNull 初始化一棵空的左偏樹Merge 合并兩棵左偏樹Insert 插入一個新節(jié)點Min 取得最小節(jié)點DeleteMin 刪除最小節(jié)點Delete 刪除任意已知節(jié)點Decrease 減小一個節(jié)點的鍵值Winter Camp 2005 演示稿2021/8/226左偏樹的操作 合并l合并操作是遞歸進行的a dist(L1)aL1R交換左右子樹并更新根節(jié)點距離合并后的右子樹距離可能大于左子樹距離Winter Camp 2005 演示稿2021/8/229左偏樹的操作 合并l合并操作的代碼如下：Function Merge(A, B)If A = NULL

4、Then return BIf B = NULL Then return AIf key(B) dist(left(A) Thenswap(left(A), right(A)If right(A) = NULL Then dist(A) 0Else dist(A) dist(right(A) + 1return AEnd FunctionWinter Camp 2005 演示稿2021/8/2210左偏樹的操作 合并l下面是一個合并的例子：61218243718700120013108261711000Merge (3, 6)Winter Camp 2005 演示稿2021/8/2211左偏樹

5、的操作 合并l下面是一個合并的例子：61218243718782617Merge (8, 6)Merge (3, 6)Winter Camp 2005 演示稿2021/8/2212左偏樹的操作 合并l下面是一個合并的例子：3718782617Merge (8, 7)Merge (8, 6)Merge (3, 6)Winter Camp 2005 演示稿2021/8/2213左偏樹的操作 合并l下面是一個合并的例子：18Merge (8,18)Merge (8, 7)Merge (8, 6)Merge (3, 6)NULL82617Winter Camp 2005 演示稿2021/8/2214左

6、偏樹的操作 合并l下面是一個合并的例子：Merge (8, 7)Merge (8, 6)Merge (3, 6)188261737701?Winter Camp 2005 演示稿2021/8/2215左偏樹的操作 合并l下面是一個合并的例子：Merge (8, 6)Merge (3, 6)11226173718861218247Winter Camp 2005 演示稿2021/8/2216左偏樹的操作 合并l下面是一個合并的例子：Merge (3, 6)02?26177371886121824310Winter Camp 2005 演示稿2021/8/2217左偏樹的操作 合并l下面是一個合并

7、的例子：Merge (3, 6)26177371886121824310201Winter Camp 2005 演示稿2021/8/2218左偏樹的操作 合并l合并操作都是一直沿著兩棵左偏樹的最右路徑進行的。l一棵N個節(jié)點的左偏樹，最右路徑上最多有 log(N+1) 個節(jié)點。l因此，合并操作的時間復(fù)雜度為：O(log N1 + log N2) = O(log N)Winter Camp 2005 演示稿2021/8/2219左偏樹的操作 插入l插入一個新節(jié)點把待插入節(jié)點作為一棵單節(jié)點左偏樹合并兩棵左偏樹時間復(fù)雜度：O(log N)MergeWinter Camp 2005 演示稿2021/8/2220左偏樹的操作 刪除l刪除最小節(jié)點刪除根節(jié)點合并左右子樹時間復(fù)雜度：O(log N)MergeWinter Ca