資料結構中的二項堆
二項堆是二項樹的集合。二項樹 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 個節點。二項樹的根透過一個按升序排列的度連結串列連結
廣告