how to Update a key in Priority Queue in O(log n )

问题:

I have been working on dijkstra's algorithm for the past one week one I have the correct running code for it in java. It is using array for the computation of standard findMin function which gives you the vertex with smallest distance.Obviously it is O(n) and Now I am looking to implement it using Priority Queue(Min Heaps)

What My thought process is:

while (there are unseen Vertex)
{

    vertex= get TheVertex WithSmallest Distance Yet;//(In can be done in O(log n) using heap)

  for this vertex {

    find all of the adjacent edges and traverse them.

    for a particular vertex which is not there in heap yet{

        Simply add it in the queue;
    }
  }
}

But if a particular vertex exists in the heap then its distance might be updated taking into account the distance of the found Min node.

Now My question is How will be update a particular element in The Heap in O(log n )time.

We cant find that element in O(1) time right?

in my naive implementation like mine it would be O(n),

So can any one suggest what can be done to handle this bottleneck? How can we update a particular vertex in the Heap in O(log n) time? (similarly how can we find a particular element in O(1) time )

回答1:

I'm aware of two basic approaches for this situation:

1. Whenever you're visiting the neighbors of a vertex, insert them in the heap no matter if they are in the heap or not. Then, when you get the vertex with smallest distance from the heap, check if it has already been removed from the heap before. If it has, then remove this one too and continue. Otherwise, mark it as removed and visit all the neighbors.

2. Keep an explicit pointer to where in the heap each element is. Then you can perform the operation known as "decrease-key" on the element that you've already located.