问题标签 [binary-heap]

所以我正在为我的班级建立一个实验室。我需要使用数组列表在 Java 中创建优先级队列。关键是每个节点都必须有一个“句柄”，它只是一个对象，其中包含与其关联的节点的索引。我知道这听起来很奇怪，但我们必须以这种方式实现它。无论如何，我的优先级队列似乎工作正常，除了句柄值显然没有正确更新，因为我没有通过句柄测试。此外，我只在调用 extractMin() 后遇到了句柄问题，所以我认为问题可能出在该方法的某个地方，但我已经经历过一百万次，对我来说看起来不错。

这是我的优先队列类：

还有我的 PQNode 类：

我的句柄类：

因为这是学校作业，我会很感激提示，但尽量不要脱口而出答案。另外，如果您愿意，我也可以发布测试，但我不知道这是否会有很大帮助。只要知道队列按原样工作，但在使用 extractMin() 后句柄不会指向正确的节点。如果您想了解更多信息，请告诉我，我知道这有点模糊。非常感谢你们。

编辑：这是我失败的特定测试

将 k 个新元素插入已经包含 n 个元素的二进制堆的时间复杂度是多少？我有一个约束，我需要以 0(k + Log n) 复杂度插入 k 个元素。

提示：使用类似于堆构建的自底向上方法。

我知道以前有人问过这个问题。我阅读了以下问题： 如何确定堆的第 k 个最大元素是否大于 x ，但我还有其他问题。我不想在那么旧的线程中发帖。所以：

给定一个 numberx和一个 number k，检查是否x大于 中的k第 -th 最小元素O(k)。

上一个问题做同样的事情，但最大堆和小于。那不是问题。

考虑一个二元最小堆：

让我们x成为 19 岁和k6 岁。

第 6 个最小的元素是 18。

如果我在另一个线程中执行算法，它将检查如下：

+计数器增加时的信号。

算法如何知道 18 是k第一个最小的数字，而不是 3？

为什么 23、80 和 88 的检查不干扰O(k)？

我正在编写一个程序来从一个普通的数组构建一个堆数组，但它不起作用。我们必须使用我用来编写rebuildHeap 函数的sudo 代码，但我不知道我做错了什么。有人能发现任何错误吗？

这是我的代码..所以首先我创建一个int数组并存储一些随机值然后我运行调用rebuildHeap的create heap函数直到堆数组完成。

已编辑，删除了数组大小..

我编写了一个名为 的结构Node，并希望能够使用指向该结构的指针作为 Phobos 中的条目BinaryHeap。但是，我不确定如何opEquals以及如何opCmp实现指向结构的指针（或者实际上，一般来说）。我无法在文档中找到任何可以帮助我的东西。谁能指出我正确的方向？

我正在尝试用 C++ 创建自己的库，并希望实现堆数据结构。

我已经为堆的插入、删除和查找编写了所有算法

我需要的是一个容器来保存堆。

我知道它们是作为数组实现的，但是由于数组必须是恒定大小，而且我不喜欢重新分配内存太多次。我应该vector用作堆的容器吗？

我已经实现了vector自己。

我正在从 java 中的二叉树创建一个堆。我的实现如下所示：

现在我想获取节点的第 n 个元素。我想，将 n 转换为二进制字符串会很聪明，弹出第一个 1，然后每个 0 向左移动，每个 1 向右移动。

这似乎不太难，但现在我的问题是，我应该如何创建一个输出，比如root.left.left.right到达第 9 个元素。我不只是想得到一个副本，这很容易（见getNode(int n)下面的函数），我想要一个对该节点的引用，所以我可以在那个地方添加一个新节点。

这在java中甚至可能吗？在 python 中，我只会创建一个".left.left.right"String 并使用run，但这在 java 中似乎是不可能的。

我有一个用于图形搜索的基于数组的二进制堆（尽管目的无关紧要）。
（索引 0 处的项目是堆的顶部。）

每隔一段时间，堆顶部的项目满足我正在寻找的标准，因此我将其弹出并保存以备后用。
目前，我只是将这些找到的项目放在一个单独的数组中并将它们返回给用户。

但是，我想知道：有什么有效的方法可以让我将项目保持在原始数组的前面，通过某种方式简单地以某种方式重新调整堆的“活动”部分的边界（即，移动起始边界一个元素的活动部分）并继续直到我完成？
天真地这样做会破坏堆的结构。

这是我最近遇到的面试问题之一。

给定一棵完全或几乎完全二叉树的根地址，我们必须编写一个函数将二叉树转换为最大堆。

这里不涉及数组。树已经构建好了。

例如，

可以有任何可能的最大堆作为输出——

或者

ETC...

我写了一个解决方案，但使用了前后顺序遍历的组合，但我猜它在 O(n^2) 中运行。我的代码给出了以下输出。

我一直在寻找更好的解决方案。有人可以帮忙吗？

编辑 ：

我的代码

从头开始构建大小为 N 的二进制堆需要 NlogN 比较平均时间，因此需要线性时间。

鉴于两个大小为 N 的二进制堆已经就位，如何在线性时间内（使用线性比较次数）构造一个包含所有 2N 个键的单个二进制堆？