左偏樹基本性質(zhì)

[性質(zhì)1] 節(jié)點的鍵值小于或等于它的左右子節(jié)點的鍵值。

即key(i)≤key(parent(i)) 這條性質(zhì)又叫堆性質(zhì)。符合該性質(zhì)的樹是堆有序的(Heap-Ordered)。有了性質(zhì)1，我們可以知道左偏樹的根節(jié)點是整棵樹的最小節(jié)點，于是我們可以在O(1) 的時間內(nèi)完成取最小節(jié)點操作。

[性質(zhì)2] 節(jié)點的左子節(jié)點的距離不小于右子節(jié)點的距離。

即dist(left(i))≥dist(right(i)) 這條性質(zhì)稱為左偏性質(zhì)。性質(zhì)2是為了使我們可以以更小的代價在優(yōu)先隊列的其它兩個基本操作(插入節(jié)點、刪除最小節(jié)點)進(jìn)行后維持堆性質(zhì)。在后面我們就會看到它的作用。

這兩條性質(zhì)是對每一個節(jié)點而言的，因此可以簡單地從中得出，左偏樹的左右子樹都是左偏樹。

由這兩條性質(zhì)，我們可以得出左偏樹的定義:左偏樹是具有左偏性質(zhì)的堆有序二叉樹。

我們知道，一個節(jié)點必須經(jīng)由它的子節(jié)點才能到達(dá)外節(jié)點。由于性質(zhì)2，一個節(jié)點的距離實際上就是這個節(jié)點一直沿它的右邊到達(dá)一個外節(jié)點所經(jīng)過的邊數(shù)，也就是說，我們有

[性質(zhì)3] 節(jié)點的距離等于它的右子節(jié)點的距離加1。

即dist( i ) = dist( right( i ) ) + 1 外節(jié)點的距離為0，由于性質(zhì)2，它的右子節(jié)點必為空節(jié)點。為了滿足性質(zhì)3，故前面規(guī)定空節(jié)點的距離為-1。

我們的印象中，平衡樹是具有非常小的深度的，這也意味著到達(dá)任何一個節(jié)點所經(jīng)過的邊數(shù)很少。左偏樹并不是為了快速訪問所有的節(jié)點而設(shè)計的，它的目的是快速訪問最小節(jié)點以及在對樹修改后快速的恢復(fù)堆性質(zhì)。從圖中我們可以看到它并不平衡，由于性質(zhì)2的緣故，它的結(jié)構(gòu)偏向左側(cè)，不過距離的概念和樹的深度并不同，左偏樹并不意味著左子樹的節(jié)點數(shù)或是深度一定大于右子樹。

優(yōu)先隊列在信息學(xué)競賽中十分常見，在統(tǒng)計問題、最值問題、模擬問題和貪心問題等等類型的題目中，優(yōu)先隊列都有著廣泛的應(yīng)用。二叉堆是一種常用的優(yōu)先隊列，它編程簡單，效率高，但如果問題需要對兩個優(yōu)先隊列進(jìn)行合并，二叉堆的效率就無法令人滿意了。本文介紹的左偏樹，可以很好地解決這類問題。

左偏樹的定義和性質(zhì)

在介紹左偏樹之前，我們先來明確一下優(yōu)先隊列和可并堆的概念。

優(yōu)先隊列，可并堆

優(yōu)先隊列(Priority Queue)是一種抽象數(shù)據(jù)類型(ADT)，它是一種容器，里面有一些元素，這些元素也稱為隊列中的節(jié)點(node)。優(yōu)先隊列的節(jié)點至少要包含一種性質(zhì):有序性，也就是說任意兩個節(jié)點可以比較大小。為了具體起見我們假設(shè)這些節(jié)點中都包含一個鍵值(key)，節(jié)點的大小通過比較它們的鍵值而定。優(yōu)先隊列有三個基本的操作:插入節(jié)點(Insert)，取得最小節(jié)點(Minimum) 和刪除最小節(jié)點(Delete-Min)。

可并堆(Mergeable Heap)也是一種抽象數(shù)據(jù)類型，它除了支持優(yōu)先隊列的三個基本操作(Insert, Minimum,Delete-Min)，還支持一個額外的操作--合并操作:

下面我們來討論左偏樹的距離和節(jié)點數(shù)的關(guān)系。

[引理1] 若左偏樹的距離為一定值，則節(jié)點數(shù)最少的左偏樹是完全二叉樹。

證明:由性質(zhì)2可知，當(dāng)且僅當(dāng)對于一棵左偏樹中的每個節(jié)點i，都有dist(left(i)) =dist(right(i)) 時，該左偏樹的節(jié)點數(shù)最少。顯然具有這樣性質(zhì)的二叉樹是完全二叉樹。

[定理1] 若一棵左偏樹的距離為k，則這棵左偏樹至少有2^(k+1)-1個節(jié)點。

證明:由引理1可知，當(dāng)這樣的左偏樹節(jié)點數(shù)最少的時候，是一棵完全二叉樹。距離為k的完全二叉樹高度也為k，節(jié)點數(shù)為2^(k+1)-1，所以距離為k的左偏樹至少有2^(k+1)-1個節(jié)點。

作為定理1的推論，我們有:

[性質(zhì)4] 一棵N個節(jié)點的左偏樹距離最多為?log(N+1)?-1。

證明:設(shè)一棵N個節(jié)點的左偏樹距離為k，由定理1可知，N ≥ 2^(k+1)-1，因此k ≤ ?log(N+1)?-1。

標(biāo)程

《數(shù)字序列》程序