1

有人知道如何为值 1-10 绘制二项式最大堆吗?我目前正在我的数据结构课程中学习堆,但是在观看了多个视频后,我仍然无法理解!而且我不确定我是否做得对。

我知道二项式堆与他们过去的堆有关,但我特别卡在最大堆上。我希望通过绘制它并看到最终结果,我将有一个更好的理解。

这是我的实现(每个“返回”都是一个新级别

10

9 8 6(所有 3 个数字都连接到 10)

7 5 4(7 连接到 8、5 和 4 连接到 6)

2 1 3(2 接 7、1 接 5、3 接 4)

我不确定将 1 和 2 放在哪里。

请让我知道我是否应该以某种方式改进我的问题以及是否需要。谢谢!

4

1 回答 1

1

According to the tag info, a binomial heap is a forest of binomial trees. And according to this wikipedia article, the number of elements in each tree must always be a power of 2. Furthermore, there can only be one tree of each size. So, for example, if there are two trees of size 4, then they need to be combined into a single tree of size 8.

So a binomial heap with 10 elements consists of two trees: a tree with 8 elements, and a tree with 2 elements. Which means your heap is as shown below. The 1 and 2 aren't connected to the other eight elements. They are in a separate tree.

enter image description here

The dotted lines can be ignored. The image source is the wikipedia article, and I just filled in the numbers.

于 2020-03-05T10:10:49.120 回答