斜堆積
斜堆積（英語：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鍵值樹的左子樹。
舉例：
外部連結[編輯]
| |||||||||||||||||||||||||||||||||||||||||||||||