问题标签 [binomial-heap]

我的目标是构建一个二项式堆。这是我现在编写的代码：

我认为简单的解决方案是将两个数组组合成第三个数组，然后调用 buildmax 程序，但我认为它效率不高，我试图从维基百科实现这个伪代码

但我不知道如何实现它，因为通常如何访问子树？另一种变体是构造优先级队列并使用插入函数先从一个数组插入，然后从另一个数组插入，但这是最优的吗？请帮我写代码有效地将这两个最大堆合并为一个

我认为我的代码可以完成这项工作，但是当我使“nsteps”高于 5 时，它会崩溃……我不断收到不同的错误……现在它只是说我的代码在高于 5 时有问题……在它说：“??? 达到 500 的最大递归限制。使用 set(0,'RecursionLimit',N) 更改限制。请注意，超出可用堆栈空间可能会使 MATLAB 和/或您的计算机崩溃。”

有人能发现问题吗？我首先调用 AmericanPutClassic(100,0)...

谢谢

有人可以解释什么是不相交集数据结构吗？或者将我链接到解释它的 YouTube 视频或文章。

几分钟前我搜索了它，我得到的只是一些数学课，其中涉及一个看起来像维恩图的图像。也许就是这样，但我不确定，所以任何帮助表示赞赏。

顺便说一句，当我被问到“如何使用二叉树来表示二叉树队列中的每个二叉树”时，这是指您必须相互堆叠的二叉树吗？就像 B1 与 B1 连接成为 B2，然后两个 B2 成为 B3，依此类推。

我正在阅读Binomial HeapPurely Functional Data Structures。

函数的实现insTree让我很困惑。这是一组代码

我的困惑在于insTree为什么它不考虑 rank t > rank t' 的情况？

在if rank t < rank t' then t::ts else insTree (link (t, t'), ts'),

1. 如果 t 的排名小于t 的排名，则将 t 放入堆中，不问任何问题
2. else有两种情况：等于和更大。
3. 对于equal，是的，我们可以链接两棵树（我们只链接两个具有相同等级的树），然后尝试将新链接的树插入堆中，没有问题。
4. 但即使是更大的情况也会有相同的平等，为什么？即使 rank t > rank t'，我们仍然链接它们吗？

编辑

我认为的过程inserting a binomial tree into a binomial heap应该是这样的：

1. 我们得到树 t 和堆
2. 在堆（实际上是一个列表）中，我们将树 t 的排名与堆中的每棵树进行比较
3. 我们找到一个与 t 的等级相匹配的缺失等级（堆中的递增顺序），我们将 t 放在那个位置
4. 我们在堆中找到一棵与 t 具有相同等级的树，然后我们链接两棵树并处理一棵rank+1新树并再次尝试将新树插入堆中。

所以，我认为正确的fun insTree可能是这样的：

二项式堆递减键的《算法导论》一书提供的接口是：BINOMIAL-HEAP-DECREASE-KEY (H,x,k)，其中H是指向树的第一个根的指针，x是节点的“索引”，其键将减少到 k。时间复杂度为 O(logn)

但是，我们通常使用链表来实现二项式堆，其中不执行搜索就无法直接访问 x，通常为 O(n)。

解决此问题的一种方法是为二项式堆中的每个节点保留一个指针，然后直接访问 O(1) 中的每个节点，但空间复杂度为 O(n)。

有人知道更好的解决方案吗？谢谢！

可以在此处找到先前的讨论。

我很难为这个陈述找到一个好的证据。我知道如何确定二叉树的数量是通过使用 n 的二进制表示来确定的。比如13个元素是1101的二进制，2^{3}+2^{2}+2^{0}所以需要3棵二叉树，ln(13) + 1 = 3.56 > 3

我只是不知道如何证明它以 log(n) 为界。一般来说，我在涉及 log(n) 的算法中遇到了许多概念

有人可以提供此声明的简洁明了的证据吗？

有没有办法用n个给定元素构建一个二项式堆，最坏情况复杂度低于O（n log n），即使用n个连续插入？（我知道插入的摊销成本是 O(1)，因此构建的平均时间复杂度更小。）对于二叉堆，有一个更有效的构建实现，它将所有 n 个元素放在二叉树中并执行 heapify/siftDown在元素的前半部分以相反的顺序。只是想知道：二项式堆是否存在类似的聪明东西？

我必须在二项式堆中插入一些值。例如 25、26、24、60、65、62。它将如下所示：

但是我必须将 25、68、65 插入同一个堆。我应该再次插入 25 还是跳过它，因为它已经存在于堆中？

这篇关于二项式堆的维基百科文章说二项式堆是二项式树的集合。

但是这个实现只使用一棵树。所以我很困惑——这个实现是二项式堆吗？如果是这样，它如何摆脱只使用一棵树？

我想实现能够快速插入并在每次插入后保持数据排序而不重复的数据结构。

我考虑过二项式堆，但我对该结构的理解是，在插入过程中它无法判断特定元素是否还在堆中。另一方面，有 AVL 树，它非常适合我的情况，但老实说，当时对我来说实施起来太难了。

所以我的问题是：是否有可能编辑二项式堆插入算法以跳过重复项？也许任何人都可以建议另一种结构？

问候:)