How to implement Prim's MST algorithm efficiently with little code/using STL with C++?

Revision en2, by LunaticPriest, 2019-07-02 23:09:49

Prim's algorithm requires a binary heap. At first, I thought I could easily use a priority queue, but it turns out that I have to reduce the weights of vertices in the priority queue, but it takes O(n) to find the vertex and modify its weight. A min-heap has the ability to reduce the weights of the vertices but it takes a lot of time to code it up, so it isn't useful for competitions. How to reduce the weight of the vertex with less complexity?

Tags minimum heap, priority queue, c++

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English LunaticPriest 2019-07-02 23:09:49 0 (published)
en1 English LunaticPriest 2019-07-02 23:09:37 534 Initial revision (saved to drafts)