数据结构中的二项堆

二项堆是二项树的集合。二项树 Bk 是一个递归定义的有序树。二项树 B0 由某个单独节点组成。

二项树 Bk 由两棵二项树 Bk-1 组成。它们彼此链接在一起。一个的根是另一个的最左子节点

下面是一些二项堆 −

二项树的一些属性如下 −

• 包含 B_k 的二项树有 2_k 个节点。

• 树的高度是 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+ 浏览量

开启你的职业

完成课程，取得认证

开始