问题标签 [binomial-heap]

我有以下树结构：

这显示了 3 个级别。我的实际问题将有 8 到 12 个级别。我有以下程序，我相信它会以正确的顺序遍历树。两个子节点向一个父节点报告。如果我们知道两个孩子，我们可以找到父母。本质上，我们想要从右到左，从下到上遍历树。数字表示需要遍历节点的顺序。

这是我相信可以实现此目的的代码：

这不是很漂亮，也不是很可扩展，因为我需要为每个附加级别添加另一个 for 循环。

三个问题：

1. 我将如何使用递归来做到这一点？
2. 有没有更可扩展的方式来做到这一点而无需递归？
3. for 循环方法或递归方法会更快

所以我已经读到，在深度 d 的顺序 k 二项式树中的节点数是 k 选择 d。但是，我不知道该结果来自何处。有人对此有简单的证明/直觉吗？

在创建二项式堆时，我知道一般程序是首先创建一个指向 nil 的头，然后慢慢插入 1 节点堆，并根据 4 种情况将具有相同程度的堆联合起来。

但是，我想问一下，给定一个大小为 n 的数组，是否有可能由于最多有 floor(lg n) + 1 个二叉树，我们根据树的数量对数组进行分区，2^0, 2^ 1, 2^2 以此类推，在每棵二叉树中冒泡，使得每棵树都满足 minheap 属性？

例如：给定数组 [4, 10, 8, 20, 5, 1, 3]

1. 如果一个一个插入，根列表是3、1和4。1有子5；4 有孩子 8 和 10，8 有孩子 20。
2. 在另一种情况下：我们有根列表 4、8 和 1。8 有子 10；1 有孩子 3 和 20，3 有孩子 5。

如果以这种方式完成，它会破坏二项式堆的全部目的吗？

Okasaki 的纯功能数据结构中描述的倾斜二项式堆支持在最坏情况下合并O(log (max (m,n)))，其中m和n是被合并队列的长度。这比在最坏情况下支持它的分段二项式队列和在最坏情况下支持它但摊销时间O(log (min (m,n)))的惰性二项式队列更糟糕[*]。这似乎是队列表示中的偏斜二进制数采用规范形式（只有一个 2，并且仅作为最低有效非零数字）的限制所固有的。是否有可能稍微放宽这个限制以获得更有效的合并？基本的挑战是不能允许一个 2 级联成另一个 2。O(log (max (m,n)))O(log (min (m,n)))

[*] 我最近还提出了一种调度二项式队列的变体，它与分段队列具有相同的最坏情况界限；该版本尚未完全实施。

我正在研究二进制、二项式和斐波那契堆排序，我发现排序需要 O(n log n) 时间。如果有人能给我一个为什么会这样的理由，那就太好了。

在了解了斐波那契堆及其操作（MAKE_HEAP、MIN、INSERT、UNION、EXTRACT_MIN、DELETE ..）后，我遇到了一个问题，我无法理解如何证明每个 h>=0 都有应用于初始堆的斐波那契堆操作会在下面的图 2-a 中产生一个堆。此外，我们如何证明对于每个 h>=0 存在应用于初始堆的斐波那契堆操作会导致以下 fgure 2-b 中的堆：

任何帮助或提示将不胜感激。

在最近的一次 CS 类测验中遇到了这个问题，但我弄错了。这些是选择：

• 3,4
• 10,13
• 10, 9
• 10

我打了 10 分，我很确定我是对的。有人可以解释为什么我不是吗？

我尝试基于此链接中的 unionNodes(BinomialHeapNode binHeap) 方法构建一个名为 union(BinomialHeap heap) 的函数，以帮助我将两个堆合并在一起。但是，当我尝试对其进行测试时，看起来 print 函数第二次返回 null以打印 heap1。更具体地说，我刚刚发现每次我在同一个堆上第二次调用 printHeap(BinomialHeap heap) 时，它什么都不会打印。我想知道发生了什么事。

我的联合方法：

我的打印方法：

上面链接中的相关方法：

还有我的测试文件：

我不明白l二项式堆中节点列表的反转：

这是什么意思？：

家长？