问题标签 [min-heap]

我想编写一个函数来告诉我给定列表是否是最小堆。

到目前为止我所写的：

我不确定基本情况应该是什么，我的递归调用是否正确？

另外，您如何控制索引最终不会超出范围？

我怎样才能证明最小堆中的最大项目必须在一个叶子上，在一个有 N 个项目的树中？

我了解最小堆的整体设计，并且可以显示/图解最大项目位于其中一个叶子（深度 N + 1 的节点> 深度 N 的节点）。我只是不确定我应该如何格式化证明。

我有一个（最小）左派堆，如下所示：

我被要求显示插入 21 的结果。我对左派堆的理解是，插入只是单个节点的合并，在这种情况下，应该将 21 与每个右父节点进行比较，直到它到达 16 的 NULL 子节点，并且应该自动放置在那里。我错了吗？它应该去别的地方吗？

我认为我想做的很清楚，但我不是泛型专家。

我在编译时收到警告：

我不明白。我错过了什么？

我最初认为这与需要检查 this.get(i) 和 this.get(parent) 是 Comparable 的实例有关......所以我添加了一个检查：

但这给出了同样的警告。

现在我正在对整个图执行 Dijkstra 算法，并通过与原始节点的总距离形成节点的最小堆。然后我从堆中删除前 n 个元素。

这让我觉得效率非常低。假设我需要找到 10 个最近的节点，而我的图有超过 100000 个节点。然后在整个图表上执行 Dijkstra 似乎是在浪费时间。但问题是我不确定是否有任何其他方法可以在不计算图中每个节点的最短路径的情况下找到前 10 个最近的节点。

有没有更好的办法？

我曾经在一次采访中被问到这个问题，我对最佳答案感到好奇。我主要受困于提供一种在比 O(n^2) 更好的时间内跟踪二维数组的解决方案。这是问题：

这是我给出的答案：

显然（如果我给出了他预期的解决方案）我会利用二维数组中的各个数组已经排序的假设。上述解决方案并没有说服我的面试官。

那么，如何以比 O(n^2) 高效的方式使用上述类来产生预期的输出？

PS：A）请注意，样本输入中的各个数组始终是排序的。B）输入可以有重复，输出应该包含重复。

我想知道java标准集合中的哪个类可以成为Min-Heap或Max-Heap的父类？我开发了 Heap 类，它可以根据策略将堆转换为最小值或最大值，并使用 add、toString、toArray 等方法来服务于标准集合方法名称的目的。我需要为 Heap 创建一个父类。我可以扩展哪个类或集合？

我正在使用左右子节点的节点结构。

我想知道是否允许最大或最小堆树具有重复值？我试图仅通过在线资源查找有关此信息的信息一直没有成功。

跟踪从以下列表中指示的堆的创建过程的每个阶段

一个。{5, 13, 2, 25, 7, 17, 20, 8, 4} 分钟堆

我希望我做对了。在继续处理下一个问题之前，我想确定这是否正确。任何意见或帮助将不胜感激。

我已经实现了一个 minHeap 类，所以我很好奇，如果不修改代码，是否可以将 minHeap 类用作最大堆？