左偏樹(shù)關(guān)系

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

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

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

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

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

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

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

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

標(biāo)程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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