问题标签 [heap]

我们得到一个 2 ^m - 1 个不同的、可比较的元素组成的数组，索引从 1 开始。

我们可以将数组视为完整的二叉树：

例如，数组

[7 6 4 5 2 3 1]

是树

现在，当被视为二叉树时，这些元素满足堆属性，一个节点大于它的两个子节点：

A[i] > A[2i] and A[i] > A[2i+1]

是否有相当快速的就地算法来打乱数组的元素，以便生成的二叉树（如上所述）是二叉搜索树？

回想一下，在二叉搜索树中，一个节点大于其所有左后代，小于其所有右后代。

例如，上述数组的重新洗牌将是

[4 2 6 1 3 5 7]

对应于二叉搜索树

所以，我试图在这里实现bottomupheap算法：http: //www.apl.jhu.edu/Classes/Notes/Felikson/courses/605202/lectures/L8/L8.html

自从我用 java 编程以来已经有一段时间了，而且我不断收到一些我不知道的错误。我想知道是否有人会通过清理一些算法步骤来帮助我。

我创建了一个带有数据和左右引用指针（或 java 调用它们的任何东西）的堆节点。输入序列是一个数组，它被转换为ArrayList. 这就是我传递给上面函数的内容。

我从 S 中删除第一个密钥并使用该密钥创建一个新节点。在我的示例中，我只使用Integers 并将键设置为数据引用。

然后我使用 S1 = S.sublist(0, S.length/2) 和 S2 = S.sublist(S.length/2, S.length)

现在我假设 H1 和 H2 是堆还是节点？这是我对我应该在java中做什么感到有点困惑的地方。

然后对于下一部分看起来我应该k.left = H1做k.right = H2

我不确定它什么时候说“k at root”。不是k根节点吗？如果是这样的话，我也会做一个向下的泡沫k吗？那么最后也会H在k这一点上吗？

抱歉，我没有要发布的代码，但我得到的错误位于递归调用的子列表中。

更新：

AnArrayList作为 S 传递。Tree定义为Tree(data, left, right)。谢谢。

谢谢！

这是我第一次在这里提问，我会尽量不破坏任何正式程序。

我正在尝试在 Mark Allen Weiss 二进制堆代码 (http : //users.cis.fiu.edu/~weiss/dsaajava2/code/BinaryHeap.java），代码差不多完成了。但是，在测试堆的时候似乎有问题；测试用例进入无限循环，我不知道为什么。我真的很感谢帮助解决这个问题。

这是测试用例的相关部分（“堆”是一个 3 堆）：

这是我的代码：

所以，我试图在这里实现bottomupheap算法：http: //www.apl.jhu.edu/Classes/Notes/Felikson/courses/605202/lectures/L8/L8.html

自从我用 java 编程以来已经有一段时间了，而且我不断收到一些我不知道的错误。我想知道是否有人会通过清理一些算法步骤来帮助我。

我创建了一个带有数据和左右引用指针（或 java 调用它们的任何东西）的堆节点。输入序列是一个数组，它被转换为ArrayList. 这就是我传递给上面函数的内容。

我从 S 中删除第一个密钥并使用该密钥创建一个新节点。在我的示例中，我只使用Integers 并将键设置为数据引用。

然后我使用 S1 = S.sublist(0, S.length/2) 和 S2 = S.sublist(S.length/2, S.length)

继承人我到目前为止：

AnArrayList作为 S 传递。Tree定义为Tree(data, left, right)。谢谢。

看起来，当传递一个空列表时，由于某种原因使用子列表时它不会认为它是一个空列表。看起来当它尝试对诸如 S.isEmpty() 之类的空对象执行任何操作时会引发错误。

谢谢！

我被困在堆排序上。我有一些代码，但我认为它非常错误，因为我很难编译它。有什么建议么？堆排序应该很容易实现，但我有一堆语法错误。这是我的代码：

我想知道 C++ 中 make_heap 的算法是什么，使得复杂度为 3*N？我能想到的通过插入元素来创建堆的唯一方法具有 O(N Log N) 的复杂性。非常感谢！

几天来，我一直试图弄清楚这一点。我对学校有一个问题，说明如下：

设 A 为最小堆。HEAP-MODIFY(A, i, k) 操作将节点 i 中的键更改为新值 k，然后重新排列最小堆中的元素。给出一个在 O(lgn) 时间内运行 n 元素最小堆的 HEAPMODIFY 的实现。

由于我们必须设计一个在 O(lg(n)) 时间内运行的算法，我知道我不能只遍历每个元素。我有以下解决方案，但我不确定它是否正确。

关于如何解决这个问题的任何建议？

这是我的场景。我想实现 A*（在 Python 中），而不必求助于线性时间最小值或操作。我需要一个堆才能有效地获得重量最低的物品。

我的第一反应是‘简单！我将使用 heapq！然后我发现生活很少像我们希望的那样简单。事实证明，这种策略对于 A* 的关键点之一不是最优的。当考虑孩子时，我需要偶尔更新已经在堆上的孩子的分数。

对于那些对 A* 的记忆有一点点流失的人来说，它的要点是我想取一个元素，修改它的权重，并修改堆以反映变化，所有这些都在亚线性时间内完成。

有什么建议么？

我有一个由二叉树组成的堆。它不是一个数组。我想知道我将如何进行排序。我知道我需要获取最后一个节点并将其放置在根并进行向下堆气泡。这部分我有。我遇到的问题是知道如何获取新的最后一个节点。有没有找到最后一个节点的算法？我是否需要跟踪每个节点上的每个父节点？

谢谢。

我正在做一些涉及堆的作业，并且我了解它们的结构。堆必须具有满足堆属性的每个节点，

最大堆属性是对于除根节点之外的每个节点 i，Heap[Parent(i)] >= Heap[i]

所以在每个节点上，较高的节点具有较高的数字，较低的节点具有较低的数字。我明白这一点。但是我看不到使用堆来简单地获取列表中最高的 n 个数字。我没有看到一种简单的方法来搜索特定值并返回节点，或者搜索 n 最小的数字（在最大堆中）。两者在二叉搜索树中都相对容易。

你为什么不只使用一个简单的二叉搜索树呢？或者更好的是，平衡的二叉搜索树？

编辑：我应该注意，这不是在寻找家庭作业问题的答案。实际的作业问题是为 insert() 和 extractMax() 函数编写并行 p 堆的伪代码。我已经回答了他们。他们只是让我意识到我并不真正了解堆。