資料結構中的二項堆


二項堆是二項樹的集合。二項樹 Bk 是一個遞迴定義的有序樹。二項樹 B0 由某個單獨節點組成。

二項樹 Bk 由兩棵二項樹 Bk-1 組成。它們彼此連結在一起。一個的根是另一個的最左子節點

下面是一些二項堆 −

二項樹的一些屬性如下 −

  • 包含 Bk 的二項樹有 2k 個節點。

  • 樹的高度是 k

  • 對於在 0 到 k 範圍內的所有 i,深度為 i 的節點數量恰好為 $$\left(\begin{array}{c}k\ j\end{array}\right)$$

二項堆

二項堆 H 是二項樹的集合。有一些屬性。

  • H 中的每個二項樹都是堆排序的。因此某個節點的鍵大於或等於其父節點的鍵。

  • H 中只有一棵二項樹(最多)其根具有給定的度。

二項堆示例

這個二項堆 H 包含二項樹 B0、B2 和 B3。它們分別有 1、4 和 8 個節點。總共 n = 13 個節點。二項樹的根透過一個按升序排列的度連結串列連結

更新於: 2020 年 8 月 10 日

3K+ 瀏覽量

開啟你的職業

完成課程,取得認證

開始
廣告