跳至內容

斜堆積

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

斜堆積(英語: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鍵值樹的左子樹。

舉例:

外部連結