左式堆

左式堆（Leftist Heaps)又稱作最左堆、左傾堆，是計算機語言中較為常用的一個數據結構。左式堆作為堆的一種，保留了堆的一些屬性。第1，左式堆仍然以二叉樹的形式構建；第2，左式堆的任意結點的值比其子樹任意結點值均小（最小堆的特性）。但和一般的二叉堆不同，左式堆不再是一棵完全二叉樹（Complete tree)，而且是一棵極不平衡的樹。

簡介

設計一種堆結構像二叉堆那樣高效的支持合併操作而且只使用一個數組似乎很困難。原因在於，合併似乎需要把一個數組拷貝到另一個數組中去，對於相同大小的堆，這將花費O(N)。正因為如此，所有支持高效合併的高級數據結構都需要使用指針。

Npl

左式堆的結點相比於一般的堆來說，增加了Npl屬性，Npl是 null path length 的縮寫，指的是從該結點到達一個沒有兩個孩子的結點的最短距離（一個孩子的結點或者葉子）。一般定義NULL的Npl為-1以使計算簡便。容易得到，任意結點的Npl是它的孩子的Npl中較小的那個結點的Npl+1.

左式堆

左式堆除了保留堆的二叉樹屬性和最小堆屬性外，有一個特徵屬性：任意結點的左孩子的Npl大於等於右孩子的Npl。這個特性決定了左式堆的不平衡性，並且明顯左邊會比較深，這就是左式堆的得來。由這個性質和上面提到的性質可以得到：左式堆任意結點的Npl為右孩子的Npl+1.

定理

沿右路共有r個結點的左式堆至少有2^r-1個結點。這個定理的證明比較容易，利用疊代即可，這裡就不贅述了。

操作方法

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

1.如果有一棵樹是空樹，則返回另一棵樹；否則遞歸地合併根結點較小的堆的右子樹和根結點較大的堆。

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

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

4.更新Npl。

左式堆的插入（Insert）很簡單，其實也就是一個單結點和原堆的合併。

左式堆的DleteMin也很簡單，就是把根結點刪除，把兩棵子樹合併。左式堆的刪除可以考慮懶惰刪除（Lazy Delete）。

時間複雜度

由於上述的操作均基於合併，而合併僅對右路做合併，而右路結點的數量為總數量的對數關係，所以左式堆的三個操作所花的時間為O(logN).

變形

左式堆的變形最常見的就是斜堆（Skew Heaps），實際上，斜堆並不是一個非常好用的數據結構，所以這裡就不講述了。.