可合併優先佇列和斜堆

可合併優先佇列

定義

隨機可合併堆（也稱為可合併堆或隨機可合併優先佇列）被定義為一種基於優先佇列的資料結構，其中底層結構也是一個堆有序二叉樹。但是，對於底層二叉樹的形狀，沒有硬性規定。

優點

  • 這種方法相較於類似的資料結構，具有一系列的功能，即優勢。
  • 它提供了比其他資料結構更簡單的方法。
  • 隨機可合併堆的所有操作都易於應用，並且其複雜度界限中的常數因子很小。
  • 此外，也不需要維護平衡條件，並且不需要節點內的衛星資訊。
  • 最後，這種結構表現出良好的最壞情況時間效率。大多數情況下，每個單獨操作的執行時間都是對數級的，且機率很高。

斜堆

斜堆（或自調整堆）被定義為一種以二叉樹實現的堆資料結構。

斜堆之所以有優勢，是因為它們能夠比二叉堆更快地合併。

與二叉堆不同，斜堆沒有結構約束，因此無法保證樹的高度是對數級的。

只需要滿足兩個條件：

  • 必須保持一般的堆序（根節點是最小值，子樹也遞迴地滿足此條件），但不需要平衡屬性（除了最後一層，所有層都必須是滿的）。
  • 斜堆中的主要操作只有合併。我們可以僅透過合併來實現其他操作，如插入、提取最小值等。

示例

假設斜堆 1 為：

假設第二個堆為：

最終合併後的樹形結構為：

遞迴合併過程

merge(a1, a2)
Let a1 and a2 be the two min skew heaps to be merged. Let a1’s root be smaller than a2’s root (If not smaller, we can swap to get the same).
We swap a1->left and a1->right.
a1->left = merge(a2, a1->left)

更新時間： 2020年1月2日

588 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

立即開始
廣告