问题标签 [binary-heap]

引用维基百科：

使用传统的二叉树数据结构来实现二叉堆是完全可以接受的。添加可以通过算法解决 的元素时，在二进制堆的最后一级找到相邻元素存在问题......

关于这种算法如何工作的任何想法？

我无法找到有关此问题的任何信息，因为大多数二进制堆都是使用数组实现的。

任何帮助表示赞赏。

最近，我注册了一个 OpenID 帐户，无法编辑我的初始帖子，也无法评论答案。这就是为什么我通过这个答案做出回应。非常遗憾。

引用米奇小麦：

@Yse：您的问题是“如何找到二进制堆的最后一个元素”？

是的。或者更准确地说，我的问题是：“如何找到非基于数组的二进制堆的最后一个元素？”。

引用抑制火：

你在问这个问题时有什么背景吗？（即，您是否正在尝试解决一些具体问题？）

如上所述，我想知道一种“找到基于非数组的二进制堆的最后一个元素”的好方法，这是插入和删除节点所必需的。

引用罗伊的话：

对我来说，使用普通的二叉树结构（使用定义为 [data, pLeftChild, pRightChild] 的 pRoot 和 Node）并添加两个额外的指针（pInsertionNode 和 pLastNode）似乎是最容易理解的。pInsertionNode 和 pLastNode 都将在插入和删除子例程期间更新，以在结构中的数据更改时保持它们的最新状态。这使 O(1) 可以访问结构的插入点和最后一个节点。

是的，这应该有效。如果我没记错的话，当它们的位置由于删除/插入而更改为另一个子树时，找到插入节点和最后一个节点可能会有点棘手。但我会试一试。

引用 Zach Scrivena 的话：

如何执行深度优先搜索...

是的，这将是一个很好的方法。我也会试试看。

我仍然想知道，是否有办法“计算”最后一个节点和插入点的位置。具有 N 个节点的二叉堆的高度可以通过取大于 N 的 2 的最小幂的对数（以 2 为底）来计算。也许也可以计算最深层次的节点数。然后有可能确定必须如何遍历堆才能到达插入点或删除节点。

我需要基本上合并一个二进制堆和线性探测哈希表来制作一个“复合”数据结构，它具有堆的功能，具有哈希表的排序能力。

我需要做的是为每个数据结构（二进制堆和哈希）创建 2 个二维数组，然后用指针将它们相互链接，这样当我更改内容时，例如删除二进制堆中的值，它也会得到在哈希表中删除。

因此，我需要让 Heap 数组的一行从 Heap 指向 Hastable，而 hashtable 数组的一行从 hashtable 指向堆。

作为 Haskell 的一个练习，我正在尝试实现堆排序。堆通常在命令式语言中实现为数组，但这在纯函数式语言中效率非常低。因此，我查看了二进制堆，但到目前为止我发现的所有内容都从命令式的角度描述了它们，并且所呈现的算法很难转化为功能设置。如何用 Haskell 等纯函数式语言高效地实现堆？

编辑：高效我的意思是它仍然应该在 O(n*log n) 中，但它不必击败 C 程序。另外，我想使用纯函数式编程。在 Haskell 中这样做还有什么意义？

我一直被困在一个问题上，想知道是否有人能指出我正确的方向：

假设使用基于指针的树表示而不是数组来表示二叉堆。考虑将二叉堆 LHS 与 RHS 合并的问题。假设两个堆都是完整的树，分别包含 (2^L - 1) 和 (2^R -1) 节点。
给出两个 O(log N) 算法来合并两个堆，一个如果 L = R，一个如果 |L - R| = 1。

这是一个家庭作业问题，我只需要指出正确的方向。

我需要有关此 minheap 代码的帮助：

好吧，代码几乎做对了所有事情，除了当它弹出屏幕上的最后一个元素时，它会打印一个随机数。你怎么看？

谢谢！

试图想出一个下限，比如最大堆中第 n 个最大的键。假设堆以数组形式布局。我认为上限的 min(2^n-2, array size -1)，但它的下限总是 0 吗？

我正在尝试从二进制堆中提取最小值，但它不起作用。这是我的 BubbleDown 代码：

看起来它只交换了几个数字，但不是全部，我不明白为什么。我试图以不同的方式重新编码它，而且已经很多次了......

我究竟做错了什么？

删除二进制堆中的最小元素后，即删除根后，我知道必须调整堆以保持堆属性。但这样做的首选方法似乎是将最后一片叶子分配给根并筛选它。

我想知道为什么我们不采用曾经是根的较小的孩子，而只是继续筛选所有的孩子？这不是相同数量的操作，那么为什么首选“assign-the-last-leaf-to-the-root-and-sift-down”方法？

斐波那契堆和二叉堆的实际应用是什么？如果您可以在使用它来解决问题时分享一些实例，那就太好了。

编辑：还添加了二进制堆。很想知道。

我正在学习数据结构课程，我们正在使用 Mark Weiss 编写的 Java 2nd Edition 中的数据结构和算法分析。在他的 BinaryHeap 实现中，他的构造函数创建了一个转换为 AnyType[] 的 Comparable[] 数组。你知道他为什么这样做而不是仅仅创建一个新的 AnyType[] 吗？

我了解 BinaryHeap 的结构，但我想跟上泛型的速度。类声明很简单，确保 AnyType 扩展了与 AnyType 或 AnyType 继承层次结构上的任何超类可比较的类型（如果 AnyType 是类型的子类并且不需要更改其 compareTo 方法即可运行）。

但是，这行 ,array = (AnyType[]) new Comparable[ capacity + 1 ];对我来说毫无意义。AnyType 不是已经是 Comparable 了吗？仅仅写作有什么后果array = new AnyType[ capacity + 1 ];？

完整的课程资源可以在他的网站上找到，但这里是我关心的部分：