Minheap and removing item if data changes in between removals

Question

I asked a question yesterday but it wasn't very clear so this is a more specific question.

I'm representing my minheap as an array. I have a good understanding of minheaps I think, but I'm fuzzy on one certain concept within. Minheaps are always supposed to have the smallest node as the root. To delete a value, the root is set to the last element in the array representation (a leaf node) and the size of the array is decremented. The root node is then placed correctly by using siftDown/PercolateDown or whatever you'd like to call it. This is super efficient. For example:

Here 29 has been taken from the last element and siftDown(1) will place it:

1. 29 is compared with 15 and 38. Exchange 29 and 15.
2. 29 is compared with 25 and 20. Exchange 29 and 20.
3. 29 is compared with 30, 29 < 30 therefore we are done.

This is all well and good, but what if in between 2 instances of removing the min, some of the other data changes? For example:

Here, then:

1. 29 is compared with 15 and 38. Exchange 29 and 15.
2. 29 is compared with 30 and 32. 29 < 30 and 29 < 32 therefore we are done.

1 is the smallest value in the tree, but it hasn't been set as the min, 15 has been. This is a huge issue for me. I am trying to implement Dijkstras algorithm, I'm also trying to use my own data structures without touching the java built in classes.

So a more relevant example for my problem would be:

For those familiar with Dijkstras, 99 represents a tentative distance of infinity and other numbers represent graph nodes which should be visited next (the node with the smallest distance, in this case 3).

A solution is to rebuild the tree every time I remove min, however this means that the power of a minheap is lost and any implementation slows down to a crawl.

Apologies if I'm not understanding this properly but I've been stuck with this for days and I really need some help.

Answer 1

You need to understand the pre-condition of the algorithm. The algorithm siftDown doesn't work for any arbitrary arrays. It only works when its left child and right child are heaps.

In your second example, the left child of the root is not a min-heap. So, the algorithm won't produce a min-heap.

There must be something wrong in your implementation if you end up in an array that violates the heap property, like the image number 3.