问题标签 [binomial-heap]

我正在寻找二项式堆的 Python 实现，我注意到代码没有实现 reduceKey。为什么在二项式堆中没有人实现 reduceKey？

对于那些非常了解这一点的人，只需阅读下面的粗体文本即可了解实际问题。

辅助功能前言：

我知道合并两个相同等级的二叉树是 O(1) 因为所有需要的就是将 T1 的头部附加为另一个的孩子。我也知道在二项式堆中插入一个顺序等于或小于最小顺序树的树是 O(logN)，因为合并的“结转”效应适用。想象一个 T_0,T_1,T_2,...,T_n（其中下标是顺序）的二项式堆，我们添加一个 0 阶的新 T'。这将导致结转 n 次合并树相同的顺序。我们知道 n = log(N)。

合并函数本身：

在合并函数中，两个堆以一种合并排序的方式逐棵树添加到一个新的堆中。我们将任一堆的最低顺序树添加到新堆中，如果两个顺序相同，则在构建后将其合并（O（1））并将其插入（O（logN））到结果树递归地。由于我们将首先插入最低顺序的树，因此合并将始终插入顺序等于或小于新堆中第一棵树的树。

发生混淆的地方：

我很困惑为什么合并函数是 O(logN)，而不是 O(logN*logN)。我们知道每个插入都是 O(logN)，并且我们有 logN 树，其中 N = N1+N2 其中 N1 和 N2 是每个起始堆中的元素数。如果我们在结构中有两个堆，这会导致每次插入新堆时都会发生插入的结转效应，那不是 O(logN * logN) 吗？

也许我在这里遗漏了一些关键的理解。任何帮助表示赞赏！如果您告诉我在我的理解中哪里出错了，请特别感谢:)

维基百科说二项式堆中的插入操作的摊销时间为 O(1)。对于单个插入操作，时间复杂度为 O(log n)。但是它的摊销时间如何变成 O(1) 呢？

我们有一个由 2016 个节点组成的二项式堆。

分解成二进制我们得到

堆由 6 个树组成，节点为 512 256 128 64 32 和 16。

但是我们如何计算某个级别的节点数呢？计算数量的公式是什么，例如 3 级中的节点是什么？

有没有最终的解决方案？谢谢

二项式堆

1. 如何将 52 之类的值插入此堆？
2. 箭头是什么意思？
3. 如何删除最小的元素？

谢谢！

鉴于二项式堆是二项式树的集合，我很难理解我们如何以升序/降序有效地打印出二项式堆的内容（取决于它是否是最小/最大堆）。

目前我使用的方法是创建堆的克隆并提取最小值（因为这是最小二项式堆），直到所有元素都被提取出来。如果我理解正确，这将导致 O(n*log(n)) 时间，这是一个相当长的过程。

有没有什么方法可以加快这个过程，或者有什么其他的方法可以按升序打印出二项式堆的内容？

假设我们有一个单树二项式堆，使得二项式树的秩为 r，因此拥有 2^r 个键。将其转换为具有 k 个最小键的 k<2^r 长度排序数组的最有效方法是什么？假设我们不能使用除惰性二项堆和二项树之外的任何其他数据结构。请注意，在每个级别上，子级都按顺序不必要地链接，因此您可能需要在某些时候进行一些比较。

我的解决方案是（假设 1<=k<=2^r）：

1. 创建一个新的空惰性二项式堆 H。
2. 将根的密钥插入堆中。
3. 创建一个新的计数器 x，并设置 x=1。
4. 对于每个级别 i=0,1,...（其中根位于级别 0）：
   • 设 c 为第 i 层的节点数。
   • 设置 x=x+c。
   • 迭代第 i 层的节点，然后：
     • 将每个节点 N 插入到 H。（在 O(1) 中）
     • 如果 x < k，则递归地对每个节点 N 进行相同的处理，通过 x 继续计数。
5. 重复 k 次：
   • 从堆中提取最小键并将其放在输出数组中。
   • 从堆中删除最小键。（摊余成本：O(1)）
6. 返回输出数组。

伪代码中可能存在一些漏洞，但我认为这个想法本身很清楚。我也设法实现了它。但是，我不确定这是完成这项任务的最有效算法。

有人知道如何为值 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 放在哪里。

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

我正在尝试在 Idris 中实现二项式堆，所以我定义了一个类型

data Bin = MSEnd | B0 Bin | B1 Bin

其中MSEnd代表“最重要的结束”（例如B0 (B1 (B1 MSEnd))代表6）。

我还定义了一个函数来将它们加在一起。我已经对此进行了测试，它按预期工作（辅助函数也是如此succ，它增加了一个二进制数）。

但是，在类型签名依赖于此plus函数的不同函数中，我得到编译器错误

根据 的定义plus，Idris 编译器似乎应该能够轻松确定它们是否相等。这里有什么问题？

二项式堆如何在查找图的连通分量时有用，它不能被使用，那为什么？