斜堆積
外觀
![本頁使用了標題或全文手工轉換](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
斜堆積(英語: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鍵值樹的左子樹。
外部連結
[編輯]
|