左式堆（Leftist Heaps)又稱作最左堆、左傾堆，是計(jì)算機(jī)語(yǔ)言中較為常用的一個(gè)數(shù)據(jù)結(jié)構(gòu)。左式堆作為堆的一種，保留了堆的一些屬性。第1，左式堆仍然以二叉樹的形式構(gòu)建；第2，左式堆的任意結(jié)點(diǎn)的值比其子樹任意結(jié)點(diǎn)值均?。ㄗ钚《训奶匦裕?。但和一般的二叉堆不同，左式堆不再是一棵完全二叉樹（Complete tree)，而且是一棵極不平衡的樹。

簡(jiǎn)介

設(shè)計(jì)一種堆結(jié)構(gòu)像二叉堆那樣高效的支持合并操作而且只使用一個(gè)數(shù)組似乎很困難。原因在于，合并似乎需要把一個(gè)數(shù)組拷貝到另一個(gè)數(shù)組中去，對(duì)于相同大小的堆，這將花費(fèi)O(N)。正因?yàn)槿绱耍兄С指咝Ш喜⒌母呒?jí)數(shù)據(jù)結(jié)構(gòu)都需要使用指針。

Npl

左式堆的結(jié)點(diǎn)相比于一般的堆來說，增加了Npl屬性，Npl是 null path length 的縮寫，指的是從該結(jié)點(diǎn)到達(dá)一個(gè)沒有兩個(gè)孩子的結(jié)點(diǎn)的最短距離（一個(gè)孩子的結(jié)點(diǎn)或者葉子）。一般定義NULL的Npl為-1以使計(jì)算簡(jiǎn)便。

容易得到，任意結(jié)點(diǎn)的Npl是它的孩子的Npl中較小的那個(gè)結(jié)點(diǎn)的Npl+1.

左式堆

左式堆除了保留堆的二叉樹屬性和最小堆屬性外，有一個(gè)特征屬性：

任意結(jié)點(diǎn)的左孩子的Npl大于等于右孩子的Npl。

這個(gè)特性決定了左式堆的不平衡性，并且明顯左邊會(huì)比較深，這就是左式堆的得來。由這個(gè)性質(zhì)和上面提到的性質(zhì)可以得到：

左式堆任意結(jié)點(diǎn)的Npl為右孩子的Npl+1.

定理

沿右路共有r個(gè)結(jié)點(diǎn)的左式堆至少有2^r-1個(gè)結(jié)點(diǎn)。

這個(gè)定理的證明比較容易，利用迭代即可，這里就不贅述了。

操作方法

左式堆的最基本的操作就是合并（Merge），之所以把它構(gòu)造成這樣一個(gè)不平衡的堆，就是為了使它相對(duì)于一般的二叉堆來說，合并變得非常地容易。左式堆的合并共有四步：

1.如果有一棵樹是空樹，則返回另一棵樹；否則遞歸地合并

根結(jié)點(diǎn)較小的堆的右子樹

和

根結(jié)點(diǎn)較大的堆

。

2.使形成的新堆作為較小堆的右子樹。

3.如果違反了左式堆的特性，交換兩個(gè)子樹的位置。

4.更新Npl。

左式堆的插入（Insert）很簡(jiǎn)單，其實(shí)也就是一個(gè)單結(jié)點(diǎn)和原堆的合并。

左式堆的DleteMin也很簡(jiǎn)單，就是把根結(jié)點(diǎn)刪除，把兩棵子樹合并。左式堆的刪除可以考慮懶惰刪除（Lazy Delete）。

時(shí)間復(fù)雜度

由于上述的操作均基于合并，而合并僅對(duì)右路做合并，而右路結(jié)點(diǎn)的數(shù)量為總數(shù)量的對(duì)數(shù)關(guān)系，所以左式堆的三個(gè)操作所花的時(shí)間為

O(logN).

變形

左式堆的變形最常見的就是斜堆（Skew Heaps），實(shí)際上，斜堆并不是一個(gè)非常好用的數(shù)據(jù)結(jié)構(gòu)，所以這里就不講述了。.