斜堆積

斜堆（英語：Skew heap）是左偏樹的一個變種。斜堆是一棵保持堆有序的二叉樹，但是它不滿足左偏性質，或者說斜堆根本就沒有「距離」這個概念——它不需要記錄任何一個節點的距離。從結構上來說，所有的左偏樹都是斜堆，但反之不然。

定義

• 僅有一個節點的樹為斜堆；
• 兩個斜堆合併的結果仍為斜堆。

合併操作

斜堆合併操作的遞歸合併過程和左偏樹完全一樣。假設我們要合併 A 和 B兩個斜堆,且 A 的根節點比 B 的根節點小,我們只需要把 A 的根節點作為合併後新斜堆的根節點,並將 A 的右子樹與 B 合併。由於合併都是沿着最右路徑進行的,經過合併之後,新斜堆的最右路徑長度必然增加,這會影響下一次合併的效率。所以合併後，通過交換左右子樹,使整棵樹的最右路徑長度非常小（這是啟發規則）。然而斜堆不記錄節點的距離,在操作時,從下往上,沿着合併的路徑,在每個節點處都交換左右子樹。通過不斷交換左右子樹,斜堆把最右路徑甩向左邊了。

遞歸實現合併

• 比較兩個堆積； 設p是具有更小的root的鍵值的堆積，q是另一個堆積，r是合併後的結果堆積。
• 令r的root是p（具有最小root鍵值），r的右子樹為p的左子樹。
• 令r的左子樹為p的右子樹與q合併的結果。

舉例。合併前：

合併後

非遞歸合併實現

• 把每個堆積的每棵（遞歸意義下）最右子樹切下來。這使得得到的每棵樹的右子樹均為空。
• 按root的鍵值的升序排列這些樹。
• 迭代合併具有最大root鍵值的兩棵樹：
  • 具有次大root鍵值的樹的右子樹必定為空。把其左子樹與右子樹交換。現在該樹的左子樹為空。
  • 具有最大root鍵值的樹作為具有次大root鍵值樹的左子樹。

舉例：

外部連結

• 斜堆(Skew Heap) by ljsspace （頁面存檔備份，存於網際網路檔案館）