java - 如果数据在两次删除之间发生变化，则最小堆和删除项目

Question

我昨天问了一个问题，但不是很清楚，所以这是一个更具体的问题。

我将我的最小堆表示为一个数组。我认为我对 minheaps 有很好的理解，但我对其中的某个概念感到模糊。 Minheaps 总是应该有最小的节点作为根。要删除一个值，将根设置为数组表示形式中的最后一个元素(叶节点)，并减少数组的大小。然后使用 siftDown/PercolateDown 或任何您喜欢的名称正确放置根节点。这是 super 有效的。例如:

这里从最后一个元素中取出 29，siftDown(1) 将放置它:

1. 29 与 15 和 38 进行比较。交换 29 和 15。
2. 将 29 与 25 和 20 进行比较。交换 29 和 20。
3. 29 与 30 进行比较，29 < 30 因此我们完成了。

这一切都很好，但是如果在两次删除最小值之间，其他一些数据发生变化怎么办？例如:

这里，然后:

1. 29 与 15 和 38 进行比较。交换 29 和 15。
2. 29 与 30 和 32 进行比较。29 < 30 和 29 < 32 因此我们完成了。

1 是树中的最小值，但尚未设置为最小值，15 已设置。这对我来说是个大问题。我正在尝试实现 Dijkstras 算法，我也在尝试使用我自己的数据结构而不触及 java 内置类。

对于我的问题，一个更相关的例子是:

对于熟悉 Dijkstras 的人来说，99 代表无限远的暂定距离，其他数字代表接下来应该访问的图节点(距离最小的节点，在本例中为 3)。

一个解决方案是每次删除 min 时都重建树，但这意味着 minheap 的功能会丢失，任何实现都会减慢速度。

如果我没有正确理解这一点，我深表歉意，但我已经坚持了好几天，我真的需要一些帮助。

Answer 1

您需要了解算法的前置条件。 siftDown 算法不适用于任意数组。只有当它的左 child 和右 child 是堆时才有效。

在你的第二个例子中，根的左 child 不是最小堆。因此，该算法不会产生最小堆。

如果你最终得到一个违反堆属性的数组，比如图像编号 3，那么你的实现一定有问题。