问题标签 [binary-heap]

我为一堆Node*s 编写了以下代码，这些代码可以在 module 中找到node：

然后我尝试在其上运行以下单元测试，其中make_leaf返回Node*使用给定参数初始化的：

测试进入我注释标记的行，然后enforce(a && b)在cmp_node_ptr. 我完全不知道为什么会这样。

给定 n 个值，我创建了一个二进制最大堆。我想知道计算以任何位置 i 为根的子树高度的公式。

我必须在二项式堆中插入一些值。例如 25、26、24、60、65、62。它将如下所示：

但是我必须将 25、68、65 插入同一个堆。我应该再次插入 25 还是跳过它，因为它已经存在于堆中？

我已经从算法介绍书中编写了 MAX-HEAPIFY(A,i) 方法。现在我想用while循环编写它而不用递归。你能帮我吗？

我一直在实现自己的堆模块来帮助我理解堆数据结构。我了解它们是如何工作和管理的，但是在执行堆排序时，我的实现比标准 python heapq 模块慢得多（对于大小为 100,000 的列表，heapq 需要 0.6 秒，而我的代码需要 2 秒（最初是 2.6 秒，删掉它）通过从 percDown 中取出 len() 语句并传递长度，减少到 2s，因此它不必每次方法调用自身时都计算 len)。这是我的实现：

popMin：弹出最小值（lst[0]）并重新排序堆

heapify：将列表原地变成堆

排序：使用上述方法对给定列表进行堆排序（非就地）

我是否错误地增加了算法/堆创建的复杂性，或者仅仅是 python heapq 模块被高度优化？我有一种感觉是前者，因为 0.6s 与 2s 是一个巨大的差异。

要从数组中获取最大 X 数量的整数，你们是否认为使用像这样的二进制堆会更快：

• 二叉堆获取最大整数
• 存储最大整数
• 从数组中删除最大的整数
• 重复直到我们从数组中获得最高的 X 数量

或者只使用快速排序并从数组中获取前 x 个整数会更快吗？

编辑：我还应该补充一点，数组不能保持排序，因为它有几个我们想要排序的变量，例如：

因此，我们可以请求从任何变量中获取最大整数。

写下来，似乎快速排序可能是一个更好的主意，尽管我想请一些意见，主要是最快的选择。

谢谢

在 Weiss 的“Java 中的数据结构和算法”中，他解释了二进制堆的插入算法

我得到了在树上移动一个洞的原理，但我不明白他是如何在 for 循环中使用这种语法来完成它的......初始化程序array[0] = x;是什么意思？看来他正在覆盖根值？这似乎是一段非常人为的代码。他在这儿做什么？

我有一个简单的算法任务，我想练习我的复杂性分析，我希望得到一些确认我是正确的。

任务是；实现一个函数，该函数接受一个 size 的数组n，并返回k最大值。实施应该是时间和空间有效的。

这是我的伪代码：

1. 创建一个大小为 k + 1 的二进制最小堆。
2. 对于数组中的每个数字；
   • 将值推送到堆上。
   • 如果堆大小现在大于 k，则弹出最小值。
3. 从堆中弹出所有值并返回结果数组。

这是我对每个步骤的时间复杂度分析：

1. 微不足道。
2. 上）
   • O(log n)
   • 微不足道
3. 好的）

所以总复杂度应该是 O(n.log n + k)？空间复杂度应该是 O(k + 1)？

此外，欢迎对我的方法提出任何批评。

提前致谢！

所以我正在尝试制作一个基于数组的通用堆，我可以在我的测试器类中使用它。我所拥有的大部分内容是基于我对树木的理解和一些在线研究以及我的教科书；两者都对我正在寻找的信息非常有限。但是，我确实设法获得了所有需要的方法，当我运行它时，我收到了这个错误：

我猜这与我如何声明和初始化我的 Comparable 数组有关，我无法弄清楚如何去做。

如果你能告诉我如何解决这个问题，我将不胜感激。谢谢

编辑：所以我编辑了我的课程，现在我这样做了data = (E[]) new Comparable[s]。那么为什么 java 不允许泛型 Array 类型，是什么使它与可以泛型的 Arraylist、Stacks、Queues 和/或 LinkedList 不同呢？

我正在研究二进制堆的自定义实现。我需要一个最小堆和一个最大堆，这样我就可以创建一个“销售 - 购买”出价系统。

我的问题是，当有新的报价（销售或购买）出现然后有购买时，“人员”应该从堆中弹出并跟踪他们的列表。我想知道如何跟踪二进制堆中的键（名称）。

例如，在外部类中，我有类似的东西。

在我的二进制堆实现中，我有这样的东西。

当我比较两个堆时，我会继续弹出直到找到匹配项（即买入价>=卖出价）。但是，当我可以返回的唯一信息是 VAL 时，我如何跟踪谁（KEY）出售和购买了