问题标签 [min-heap]

下面是我使用基于 0 的数组和书中的标准逻辑构建最小堆的程序。我正在使用2*i+1左孩子和2*i+2右孩子，因为它是一个基于零的数组，但我仍然得到错误的输出。我错过了什么？

我写了一个小片段，以找到最小堆中两个节点之间的最短路径。

有没有更好的方法可以用更好的平均情况来做到这一点？只是学习。

编辑：

为了简单起见，假设这个数组是一个二进制堆。根是 1，假设 5 和 7 之间的最短路径由 shortestPath(5, 7) 给出。

这段代码是为了确定二叉树是否是最小堆，我NullPointerException在公共静态布尔 isMinHeap 中的第三个 if 语句中不断得到一个，我不确定为什么我一直得到这个异常，因为我认为代码是有效的由于上述中断。

我正在尝试实现一个优先级队列，该队列将按其大小顺序对 HashSet 进行排序（即最小的 HashSet 将具有最高优先级）。

我如何在 Java 中实现它？

下面是我尝试按优先级编号（最高优先）成功排序 HashSet。

我的主要方法：

我的 PriorityQueue 课程

我想用浮点数填充二进制堆——更具体地说，我想实现一个最小堆。

浮动似乎不支持Ord，因此不能开箱即用。到目前为止，我试图包装它们的尝试都失败了。然而，似乎如果我可以包装它们，那么我也可以Ord以这样一种方式实现，它可以有效地形成BinaryHeap一个最小堆。

这是我尝试过的包装器示例：

问题是pop返回值，就好像它是一个最大堆一样。

我到底需要做什么才能将值填充BinaryHeap为f64最小堆？

我对堆和 PQ 的概念不熟悉。所以我试图使用最小堆使用 PQ 来实现堆栈。我正在尝试实现以下方法：

1. 流行音乐
2. 流行音乐
3. 是空的
4. 最佳
5. 尺寸

下面是代码：

现在，我的查询是top =3 的值。它是否正确 ？它不应该是输入的最后一个值，即 4 吗？我的理解是，当我们正在实现一个堆栈时，一瞥应该会给出堆栈顶部的元素，该元素应为 4 而不是 3。

如果我的实施不正确或我的理解，有人可以告诉我吗？

考虑以下示例。我将随机数添加到最小堆，同时我以相同的顺序将相同的数字添加到最大堆。所以最后这两个堆将具有相同的数字，不同的是一个是最小堆，第二个是最大堆。

现在问题来了：

如果我决定从最大堆中删除最大元素，那么最大堆中的最大元素是否总是在最小堆的底部？如果不是，那么另一个问题是，如果我想从最小堆中删除该最大元素，并将他与最小堆的最后一个元素交换，删除最后一个元素，我是否需要运行必须比较该切换元素的操作带着他的孩子为了修闵堆？还是总是将其与父级进行比较以修复最小堆？

我正在创建 arc 类型的对象并将其插入堆中，堆中应该按升序对它们进行排序但不工作输出应该是

但它给了我这个

这是 Arc 类

这是最小堆类

我正在尝试实现最小堆的就地算法。我将 BST 转换为排序链表，以下是代码片段

}

调试后，我得到了正确的输出，但是在以无序方式遍历它时，我得到了堆栈溢出异常。

我正在阅读关于CLRS 第三版（第 662 页）中的 Dijkstra 算法。这是书中我不明白的部分：

如果图足够稀疏——特别是E = o(V^2/lg V)——我们可以通过使用二进制最小堆实现最小优先级队列来改进算法。

为什么图形应该是稀疏的？

这是另一部分：

每个 DECREASE-KEY 操作都需要时间O(log V)，而且这样的操作最多还有 E 个。

假设我的图表如下所示：

我想计算从 1 到 6 的最短路径并使用最小堆方法。所以首先，我将所有节点添加到最小优先级队列中。建立最小堆后，最小节点就是源节点（因为它与自身的距离为0）。我提取它并更新其所有邻居的距离。

然后我需要调用decreaseKey距离最小的节点来创建一个新的堆最小值。但是我怎么知道它在常数时间内的指数呢？

节点

最小优先级队列