问题标签 [binomial-heap]

我需要知道二叉堆和二叉堆之间的主要区别，而不管二叉堆只能有两个孩子（树表示）和二叉堆可以有任意数量的孩子的结构差异。

我实际上只是想知道以这样的方式组织二项式树结构有什么特别之处，即第一个孩子在一个节点上，第二个有两个，第三个有四个，依此类推？

如果我们对堆使用一些正常的树而没有两个孩子的限制，然后应用联合程序并只使一个堆成为其他堆的左孩子怎么办？

我最近刚刚启动了一个项目，其中包含一些已经编写的代码。我决定研究他的实现，发现他实现了一个带有单链表的优先级队列。

我对 SLL 的理解是，由于您可能必须遍历整个列表，因此实现它的效率很低，这就是首选堆的原因。但是，也许我错过了它背后的某种推理，并且想知道是否有人曾经为优先队列选择 SLL 而不是堆？

以下文字来自二项式队列文章。

尽管 leftist 和 skew heaps 在每次操作 O(log n) 时间内都有效地支持合并、插入和 delete_min，但仍有改进的余地，因为我们知道二进制堆支持每次操作的平均时间不变的插入。二项式队列在每个操作的最坏情况时间 O(log n) 内支持所有三个操作，但插入平均花费恒定时间。

在上面的文字中，作者所说的每次操作的平均时间不变是什么意思？它与二项式队列插入平均需要恒定时间有何不同？

每次操作的恒定平均时间和平均恒定时间之间有什么区别？

我在这里阅读有关二项式队列操作的信息。

在链接的底部，它被称为

二项式队列的实现

1. deletemin 操作需要能够找到根的所有子树。因此每个节点的子节点应该是可用的（比如一个链表）
2. deletemin 要求子节点按其子树的大小排序。
3. 我们需要确保很容易合并tress。只有大小相同的两棵二叉树才能合并，因此树的大小必须存储在根中。合并时，其中一棵树成为另一棵树的最后一个子节点，因此我们应该跟踪每个节点的最后一个子节点。一个好的数据结构是循环双向链表，每个节点的形式如下：

在上面作者的意思是“排名No. Of？”任何人都可以举例说明。

在二项式堆结构中，我们只知道指向最小节点的指针，但是如何减少任意节点的键呢？在这种情况下，首先，我应该找到这个节点，然后用 O(lgN) 时间执行交换。

我在网上搜索，很多人指出如何减少节点，但没有提到如何访问这个要减少的节点。

编辑：

我应该使用指向堆的每个节点的指针。

有人可以解释一下，在标题中提到的那些中，我应该如何决定是否使用一个或另一个堆实现？

我想要一个答案来指导我根据问题选择有关结构性能的实现。现在，我正在做一个优先级队列，但我不仅想知道最适合这种情况的实现，还想知道允许我在任何其他情况下选择实现的基础知识......

另一件要考虑的事情是我这次使用的是haskell，所以，如果你知道任何可以改进这种语言实现的技巧或东西，请告诉我！但和以前一样，也欢迎对使用其他语言的评论！

谢谢！对不起，如果这个问题太基本了，但我根本不熟悉堆。这是我第一次面临实施一个任务的任务......

再次感谢！

我有一个具有以下定义的类，

我们在大学里学习二项式堆，我已经在代码中实现了合并和插入算法。至少，当我暂停 Visual Studio 并查看“Locals”时（通过将鼠标悬停在变量上），我可以看到预期的数据。

作为一个实验，我在标准的“二项式节点”中添加了 2 个额外的变量。它们是 x_point 和 y_point。现在在程序执行期间我看到了这个，

请注意我在上面指出的区域。它应该代表同一个节点，但正如我们所见，x_point 的值是不同的。（在其他情况下，y_point 不同）

有谁知道为什么会这样？据我了解，如果它代表同一个节点，则数据应该是相同的。但它不是——这意味着它不是同一个节点。这怎么可能？如果我忽略我的“额外” x_point 和 y_point 变量，代码运行完美！事实上，我什至都不知道这是个问题。

从我的代码片段中看不到它，但 x_point 和 y_point 是我在类定义之外编辑的唯一值。其他的，虽然是公开的，但只能从中读取。

编辑：这是我制作的代码，

我使用表单窗口从用户那里获取数据以填充堆。输入在这里，

我希望代码不是太糟糕？

据我所知，存在一个二项式堆或所谓的可合并堆，用于合并两个堆。我的问题是，如果我将这两个堆复制到一个大数组中然后执行堆构建过程，而不是将这些堆动态合并到一个堆中，这是否是一个好方法？

因为我不知道如何仅通过堆操作使用两个堆来创建一个堆。请告诉我这是否不是一个好方法，或者如果可以，请给我一些链接，其中实现了具有合并操作的二项式堆。

我的图形实现的 Vertex 类中有一个名为 handle 的成员。它是这样声明的：

...句柄来自我们的 TA 向我们展示的 boost::heap 库。所以，它所在的 Graph.h 文件有

当我编译一个使用这个句柄成员的程序时，我得到这个错误：

Graph.h:80：错误：预期的 `;' 在“处理”之前

马上，任何人都可以看到缺少的东西（或者我需要更仔细地查看周围的线条吗？）？

Okasaki 在Purely Functional Data Structures（第 22 页）中的实现分为两部分：一是合并森林，一是传播进位。这让我觉得比一次性版本更难分析，也可能更慢。我错过了什么吗？

冈崎的实现：

这让我觉得很难分析，因为你必须证明传播所有进位的成本的上限（见下文）。我想出的自上而下的合并实现更明显是 O(log n) 其中 n 是较大堆的大小：

证明 Okasaki 的实现是 O(log n)：如果进位是“昂贵的”（需要一个或多个链接），那么它会产生零。因此，下一个昂贵的进位将在到达该点时停止。因此，传播所有进位所需的链接总数不超过传播前二进制表示的总长度，该长度以 ceil(log n) 为界，其中 n 是较大堆的大小。