priority_queue questions

[mconell]

Hi. I was trying to code the algorithm from here: http://en.wikipedia.org/wiki/Prim%27s_algorithm

But I don't know how to update a value in a priority_queue in O(log n) where n is the amount of elements in the priority_queue.
First question: Is it possible to update a value in a priority_queue (from stl) in O(log n) ?

I couldn't found anything of how to do it and this makes me think that it could be done with a set.
With a set I can get the maximum/minimum element in O(1) with .begin() or .rbegin().
Also I can delete/insert in O(log n). Besides that it is possible to update one value in O(log n) by deleting and then inserting the element.
Second question: Why using priority_queue instead of set?

Thanks in advance

[sohguanh]

O(log n) are computer science terms called Algorithm Complexity. It would be wise for a computer science researcher to answer your concern. I did quite badly in this subject in my Uni studies and that is why I am a STL library user rather than the STL implementers :P

[ne555]

You only have access to the top of the queue, so I think there is no way of updating a value in O(log n)
However if you work with the edges, you don't need to do that.

Choose an edge (u, v) with minimal weight such that u is in Vnew and v is not (if there are multiple edges with the same weight, any of them may be picked)

Every time you add a vertex to the tree, push his edges to the priority queue.
To choose a vertex, just pop the edge from the queue and test if is valid (if one extreme was not already visited)

[ne555]

I think that a priority queue is implemented as a heap.
If you change a value you can keep the heap property by:
a_ swapping with his father until me < father and
b_ swapping with my biggest son until me > biggest_son

This will take O(log n) to perform so, why is not implemented?

[sohguanh]

This will take O(log n) to perform so, why is not implemented?

Hmm... this you need to check with the STL implementers. I think Dinkumware sell C++ STL libraries so maybe you can direct your question to them ? :P

[mconell]

Thanks for the replies!
ne555: It's true that I can use the edges and every time I add a vertex I can just push his edges to the priority queue. But in this case, the bound on the algorithms is not O(E log V) but O(E log E) or am I missing something? Because if I add edges to heap, then it's possible to put into the heap until O(E) elements.

By the way... I couldn't find any reason for having a priority_queue when the set have better performance and more operations (like insert/delete any element in O(log N) ). Is it just about having another interface? I don't get it.


Thanks again! :D