问题标签 [heap]

我正在考虑以下问题（我认为这是众所周知的/标准）：

验证在二进制最小堆中列出 k 个最小元素是 O(k)。

我正在考虑遍历BFS中的大最小堆，维护一个最小堆而不是一个简单的队列。最初，辅助最小堆包含我的大最小堆的根。在每个步骤中，我提取最小值并添加其所有子项（最多 2 个）。该算法在辅助最小堆上的 k 个提取分钟后停止。辅助最小堆的大小是 O(k)（对于提取的每个最小键，我插入它的孩子，最大 2）。

问题是 extract-min 具有 O(log k) 复杂度，因此该算法具有 O(k log k) 复杂度。我必须在 O(k) 中找到一个。

你有什么我可以使用的想法/论文吗？

谢谢！

我搜索了最小最大堆算法实现，我记得关于这个结构的一些事情，她的实现是在一个堆上。堆树中的偶数层（楼层）是最小颜色的，其余节点是最大颜色的。我记得这个工作的一些草稿，但我搜索了一些关于它的好文档或一些C代码C++片段，我找不到谷歌的任何有用信息，我认为这是一种非广泛使用的算法。

问候并感谢您提供有用的答案。

我目前正在为数据结构和算法课程分配作业。
我必须从给定的堆中删除节点；

我的问题是我会向右，向左倾斜还是有关系？

对于我的任务，我正在构建一个堆，堆的数据来自一个文件。其中一个功能是获取数据，但我无法理解 ifstream read() 函数，因此我遇到了一个非常讨厌的错误，这就是我所拥有的：

我收到的错误是：

任何帮助将非常感激！

我目前正在开发一个在添加和删除值时显示堆的小程序。我将堆实现为整数树 - IntTrees。我正在为倾斜堆编写代码，而“添加”方法给我带来了一些麻烦。add 方法通常有效，但偶尔会在添加值时导致堆栈溢出错误，我似乎无法弄清楚原因。

这是我为 add 方法编写的代码

't' 是一个实例变量——堆本身。

这段代码中是否存在会导致堆栈溢出错误的内容，或者问题可能在程序的其他地方？谢谢！

在我的作业中，我知道我需要使用我的堆删除函数来返回要打印的变量。但是任务中的要求很模糊，我很好奇是否有人可以给我一个更好的解释。我对如何使用第二个或第三个参数感到很困惑，我知道需要进行一些排序，我需要两个 for 循环，但在那之后我迷路了。这是作业的内容：

此函数从堆结构中检索项目并将它们打印到标准输出上。要从堆结构中检索单个项目，它会调用 remove 函数。此函数的第一个参数是堆结构的向量，第二个参数是在标准输出上分配的打印项的大小，第三个参数是单行上的最大打印项数，最后一个参数是谓词.

这是我的代码：

设置

我有一个堆，其中包含存储在 s 的二维数组heapArray中的intLevels级别和e元素（两者），它又高又宽。出于假设的目的，假设我输入了 1、2、3、4、5、6、7、8 和 9。堆看起来像这样：intObjectintLevelsMath.pow(2, intLevels)

如果你用一系列java.util.Arrays.toString(Object[] a)s 打印它，它看起来像这样：

有谁知道如何获取这些信息并从中创建一个 JTree？对于不知道的人来说，JTree 的工作原理很像链表。您有一个根节点，可以向其中添加更多节点，并且可以在这些节点上添加其他节点。我知道一个事实，如果我正在处理的唯一堆是这个堆，我将能够以这种方式制作树：

这导致一棵树看起来像：

编辑

我发现实现了答案的buildTree(List<Object[]>)方法：

它似乎仍然不起作用；树仍然是空的。

问题

有谁知道用给定信息将这个二维数组制作成 JTree 的相对简单但灵活的方法？如果正确实施，将 1、2、3、4、5、6、7、8 和 9 输入到这个树/堆/数组应该最终得到与我上面显示的具体方式相同的结果。

我正在尝试概述一种算法来确定我的数组是否是最小堆。是否有任何文件可以帮助我解决这个问题？我在 Apache 的网站上找到了它的一个函数，但它并没有准确地显示该函数是如何工作的；只是存在一个函数（BinaryHeap（boolean isMinHeap））。

我有这些程序

当我运行它编译正常但运​​行停止后它运行异常为什么？请帮忙看看这段代码

来自维基百科。

我有 100 组 A 对象，每组对应一个查询点 Qi 1 <= i <= 100，.

在我的算法的每次迭代中，我选择一个查询点 Qi 并从相应的集合中提取具有最小距离值的对象。然后，我必须在所有 100 个集合中找到这个特定对象，使用它的 id 进行搜索，然后删除所有这些对象。

如果我为每组对象使用一个堆，那么使用MIN(distance). 但是，我将无法在使用 id 搜索的其他堆中找到相同的对象，因为堆是使用距离值组织的。此外，更新堆是昂贵的。

我考虑过的另一个选择是map<id, (distance, x, y)>为每组使用一个。这种按 id 搜索（查找操作）的方式很便宜。但是，提取具有最小值的元素需要线性时间（它必须检查地图中的每个元素）。

是否有任何我可以使用的对我需要的操作都有效的数据结构？

• extract_min（距离）
• 查找（ID）

提前致谢！