左偏堆（Leftist Heap）

定義

\text{shortest}(x)=\begin{cases} 0, & \text{x 為外部節點（空）}\\ 1+\min\{\text{shortest}(x.\text{left}),\;\text{shortest}(x.\text{right})\}, & \text{否} \end{cases}

Leftist tree（左傾樹）：對每個內部節點 \(x\)，\(\text{shortest}(x.\text{left})\;\ge\;\text{shortest}(x.\text{right}).\)
Leftist heap：同時滿足 \(\text{key(parent)}\;\le\;\text{key(child)}\quad\text{(min-heap)}\) 與上式左傾條件。

備註：Leftist heap 不是完全二元樹（Complete BT）。

對任意 leftist tree，令 \(S(x)=shortest(x)\) 到外部節點(leaf or null node)。若根為 \(x\) 且，則

N(x) \;\ge\; 2^{S(X)}-1.

亦即：\(k\le \lfloor \log_2(N(x)+1)\rfloor\)，所以右鏈長度 \(=O(\log N)\)。

Base \(k=0\)：\(x\) 為外部節點，\(N(x)=0\ge2^{0}-1=0\)，成立。

Induction step：假設對所有 \(k\) 皆成立。若 \(\text{shortest}(x)=k\)，依 leftist 性質，至少有一邊子樹（左或右）滿足 \(\text{shortest}(\text{sub})=k-1\)

由歸納假設，該子樹之節點數 \(\ge 2^{k-1}-1\)。另一邊子樹的節點數 \(\ge 0\)。因此

\begin{aligned} N(x) &= 1 + N(\text{left}) + N(\text{right})\\[2pt] &\ge 1 + (2^{k-1}-1) + 0\\[2pt] &= 2^{k-1}\\[2pt] &\ge 2^{k}-1\quad (\text{當左右皆有 }\text{shortest}=k-1\text{ 時可達 } 2^{k}-1). \end{aligned}

更緊的標準推法（兩邊最短皆為 \(k-1\)）可得：

N(x)\ge 1 + (2^{k-1}-1) + (2^{k-1}-1) = 2^{k}-1.

故命題成立。

\text{shortest}(H)=1+\min\{\text{shortest}(H.\text{left}),\;\text{shortest}(H.\text{right})\}.

為何是 \(O(\log n)\)：遞迴只沿右鏈下行，且左傾條件保證右鏈長度 \(=O(\log n)\)，因此合併與其餘兩操作皆為 \(O(\log n)\)。