Minheap and item deletion if data changes between deletes

Question

I asked a question yesterday, but that was not very clear, so this is a more specific question.

I present my minheap as an array. I think I am well versed in fraud, but I am unclear on one specific concept inside. Minheaps should always have the smallest node as the root. To remove a value, the root is set to the last element in the array view (leaf node), and the size of the array is reduced. The root node is then placed correctly using siftDown / PercolateDown or whatever you would like to name. It is super efficient. For instance:

Here 29 was taken from the last element and siftDown (1) will put it:

• 29 compared to 15 and 38. Exchange 29 and 15.
• 29 compares with 25 and 20. Exchange 29 and 20.
• 29 compare with 30, 29 <30 so we are done.

This is all good and good, but what if between two instances of the min deletion, some other data changes? For instance:

Here:

• 29 compared to 15 and 38. Exchange 29 and 15.
• 29 is compared with 30 and 32. 29 <30 and 29 <32 so we are done.

1 - the smallest value in the tree, but it was not set as min, 15 was. This is a huge problem for me. I am trying to implement the Dijkstras algorithm, I am also trying to use my own data structures without affecting the Java built-in classes.

So a more suitable example for my problem would be:

For those familiar with Dijkstras, 99 represents the preliminary infinity distance, and the other numbers are the nodes of the graph, which should be visited as follows (the node with the smallest distance, in this case 3).

The solution is to rebuild the tree every time I remove min, but that means the mineap's power is lost, and any implementation slows down to a traversal.

Sorry if I do not understand this correctly, but I am stuck with this for several days and I really need help.

Answer 1

You need to understand the prerequisite of the algorithm. The siftDown algorithm siftDown not work for any arbitrary arrays. It only works when its left child and right child are heaps.

In your second example, the left root child is not a mini-heap. Thus, the algorithm will not generate a mini-heap.

There should be something wrong with your implementation if you end up in an array that violates the heap property, such as the image number.