左偏堆的特點及其應用

1、左傾樹的特點及應用，廣東省中山一中黃園河2。左傾樹的定義，左傾樹是一個可合并堆，它不僅支持優(yōu)先級隊列的三個基本操作(插入、刪除、取最小節(jié)點)，還支持一個非常特殊的操作合并操作。左傾樹是一個堆有序的二叉樹。左傾的樹滿足了左派的屬性。左偏樹的定義左偏屬性定義左偏樹中的外部節(jié)點是左子樹或右子樹為空的節(jié)點。節(jié)點I的距離(dist(i)定義為從節(jié)點I到其后代中最近的外部節(jié)點的邊數。任何節(jié)點的左子節(jié)點的距離不小于右子節(jié)點的距離(左偏移屬性)。根據左偏屬性，節(jié)點的距離等于以節(jié)點為根的子樹的最右邊路徑的長度。4，左傾樹的性質，定理：如果左傾樹有N個節(jié)點，左傾樹的距離不應超過對數(N 1) -1。最右邊的路徑：

2、 ACG最右邊的路徑節(jié)點數=3距離=2，左傾樹的最大距離為8個節(jié)點：log(8 1) -1=2，5，左傾樹的操作，左傾樹支持以下操作：MakeNull初始化一個空的左傾樹合并兩個左傾樹插入一個新的節(jié)點最小值得到最小節(jié)點刪除最小值刪除最小節(jié)點刪除任何已知節(jié)點減少一個節(jié)點的鍵值，6， 左傾樹合并的操作，合并操作是遞歸的，合并T1和T2左傾樹，首先合并T1的右子樹和T2，7。 合并左傾樹，這是遞歸的，首先合并T1的右子樹和T2，8。合并左樹，這是遞歸的，交換左右子樹并更新根節(jié)點距離，合并后，右子樹距離可能大于左子樹距離。合并操作代碼如下：函數合并(a，b)如果a=空，則返回b如果b=空，則返回a如果

3、鍵(b) dist(左(a)然后交換(左(a)，右(a)如果右(a)=空，則dist (a) 0否則dist (a) dist(右(a) 1返回一個結束函數，10。以下是合并的示例：11。以下是合并的示例：12。以下是合并的示例：13。以下是合并的示例：18、NULL、14。下面是一個合并的例子。15，左傾樹操作合并，下面是一個合并示例：1，1，2，26，17，37，18，8，7，16，左傾樹操作合并，下面是一個合并示例：0，2，17、左傾樹被合并。以下是合并的示例：3、10、2、0、1、18。合并操作總是沿著兩個左傾樹的最右邊的路徑執(zhí)行。有N個節(jié)點的左傾樹在最右邊的路徑上最多有N(1)個節(jié)點。因此，合并操作的時間復雜度為：0(對數N1對數N2)=0(對數N)，19，插入一個新節(jié)點，將待插入的節(jié)點作為單節(jié)點左偏樹，合并兩個左偏樹：0(對數N)，20，刪除左偏樹，刪除最小節(jié)點，刪除根節(jié)點合