昨天我问了一个问题，但这还不是很清楚，所以这是一个更具体的问题。
我将我的minheap表示为数组。我对Minheap有很好的理解，但是我对其中的某个概念很模糊。 Minheap始终应该以最小的节点为根。要删除值，请将根设置为数组表示形式中的最后一个元素(叶节点)，并减小数组的大小。然后使用siftDown/PercolateDown或您要调用的任何东西正确放置根节点。这是超高效的。例如:
这里的29是从最后一个元素中提取的，而siftDown(1)将放置它:
这一切都很好，但是如果在两次删除最小值之间有两次其他数据更改，那该怎么办呢？例如:
然后，在这里:
1是树中的最小值，但尚未设置最小值，因此设置为15。对我来说，这是一个巨大的问题。我正在尝试实现Dijkstras算法，也试图在不接触内置类的Java的情况下使用自己的数据结构。
因此，与我的问题更相关的示例是:
对于熟悉Dijkstras的人来说，99表示无穷大的暂定距离，其他数字表示下一个应该访问的图节点(距离最小的节点，在这种情况下为3)。
一种解决方案是每次删除min时都重建树，但这意味着minheap的功能会丢失，并且任何实现都会减慢爬网速度。
抱歉，如果我不能正确理解它，但是我已经坚持了好几天，我真的需要一些帮助。
最佳答案
您需要了解算法的前提条件。算法siftDown不适用于任何任意数组。它仅在其左子对象和右子对象为堆时才有效。
在第二个示例中，根的左子级不是min-heap。因此，该算法不会产生最小堆。
如果您最终遇到违反堆属性的数组(例如图像编号3)，则实现中肯定有问题。
关于java - 如果两次移除之间的数据发生变化，则最小堆和移除项，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/36719734/