左偏堆的特點(diǎn)及其應(yīng)用

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

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

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

4、turn 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/3/910左偏樹(shù)的操作 合并l下面是一個(gè)合并的例子：61218243718700120013108261711000Merge (3, 6)Winter Camp 2005 演示稿2021/3/911左偏樹(shù)的操作 合并l下面

5、是一個(gè)合并的例子：61218243718782617Merge (8, 6)Merge (3, 6)Winter Camp 2005 演示稿2021/3/912左偏樹(shù)的操作 合并l下面是一個(gè)合并的例子：3718782617Merge (8, 7)Merge (8, 6)Merge (3, 6)Winter Camp 2005 演示稿2021/3/913左偏樹(shù)的操作 合并l下面是一個(gè)合并的例子：18Merge (8,18)Merge (8, 7)Merge (8, 6)Merge (3, 6)NULL82617Winter Camp 2005 演示稿2021/3/914左偏樹(shù)的操作 合并l下面是

6、一個(gè)合并的例子：Merge (8, 7)Merge (8, 6)Merge (3, 6)188261737701?Winter Camp 2005 演示稿2021/3/915左偏樹(shù)的操作 合并l下面是一個(gè)合并的例子：Merge (8, 6)Merge (3, 6)11226173718861218247Winter Camp 2005 演示稿2021/3/916左偏樹(shù)的操作 合并l下面是一個(gè)合并的例子：Merge (3, 6)02?26177371886121824310Winter Camp 2005 演示稿2021/3/917左偏樹(shù)的操作 合并l下面是一個(gè)合并的例子：Merge (3, 6

7、)26177371886121824310201Winter Camp 2005 演示稿2021/3/918左偏樹(shù)的操作 合并l合并操作都是一直沿著兩棵左偏樹(shù)的最右路徑進(jìn)行的。l一棵N個(gè)節(jié)點(diǎn)的左偏樹(shù)，最右路徑上最多有 log(N+1) 個(gè)節(jié)點(diǎn)。l因此，合并操作的時(shí)間復(fù)雜度為：O(log N1 + log N2) = O(log N)Winter Camp 2005 演示稿2021/3/919左偏樹(shù)的操作 插入l插入一個(gè)新節(jié)點(diǎn)把待插入節(jié)點(diǎn)作為一棵單節(jié)點(diǎn)左偏樹(shù)合并兩棵左偏樹(shù)時(shí)間復(fù)雜度：O(log N)MergeWinter Camp 2005 演示稿2021/3/920左偏樹(shù)的操作 刪除l刪除最小節(jié)點(diǎn)刪除根節(jié)點(diǎn)合并左右子樹(shù)時(shí)間復(fù)雜度：O(log N)MergeWinter Camp 2005 演示稿2021/3/921總結(jié)l左偏樹(shù)的特點(diǎn)：時(shí)空效率高編