Priority queue and Prim's Algorithm

3
votes

I have gone through the C++ reference manual and am still unclear on how to use the priorityqueue data structure in STL.

So, basically I have been trying to implement my own using heaps.

I am doing this for implementing Prim's algorithm.

Vector <int, int> pq;

This is my priority queue. The first field is the node and the second field the weight to the existing tree.

I plan to modify the values of weight in pq every time a new node is added to the tree by updating the weights of its neighbour nodes.

  • How do I access the individual elements of this vector? I also need to be able to delete elements at will.

Is this a good way to implement a priority queue? what if I want to add another field to the container, namely 

Vector<int, int, int> MST
  • How would I access the third element? I want to store the resulting MST this way such that the first two fields represent the vertices forming the edge, and the third the weight.

It would also help if someone could tell me how to assign elements to this vector using push_back.

  • Also, would the conventional C++ STL priority queue help in this as I need to update the priority values each time a new element is added to the MST? Would it self-correct itself according to the priority when values are modified?

  • One other question, these Vectors, when I pass them to a function, and try to make changes, is it a pass by value or pass by reference - Or, are the changes reflected outside the function?

2
c++algorithmstl
Are you referring to the ancient and outdated ARM with "the C++ reference manual"? - PlasmaHH
If you mean std::vector as Vector, STL vector could have only one template parameter for element type (in fact it also has allocator template parameter). You can use std::vector<std::pair<int,int>> for your purposes instead. cplusplus.com/reference/vector/vector - vard
@PlasmaHH : I actually meant the cplusplus.com site as reference. I thought that was legit :) - Floose
@vard: Yes. I mean std::vector. Well, I need to add both the edges and the weight and be able to access the elements individually to print. - Floose
@Floose in fact you want to have indexed priority queue, am I right? - vard

2 Answers

5
votes

In Prim's algorithm the random access to elements not needed. You just need to skip elements from the queue which connect already connected and pass forward.

So the algorithm looks as follows:

  1. choose a node N
  2. add all edges from N to the PQ
  3. pop a minimal cost edge from PQ
    • if it connects nodes which are already in the tree, skip it
    • otherwise add this edge to the tree, call the new node N and go back to point 2.

After adding the node just check if size of the tree is already size of graph - 1. If so then finish.

Note that the only operations on PQ are add_element and pop_minimum - thus std::priority_queue will work.

2
votes

Firstly, std::vector<int,int> isn't valid - the second type argument is an (optional) allocator, and int is not an allocator. If you're using a different underlying container, please say what it is. I'll assume you want to work with std::vector for now.

Secondly, std::priority_queue doesn't support the operations you want (access and delete arbitrary elements), so you can't use that.

You can use the underlying vector directly, and the heap algorithms (std::make_heap etc.) to sort it:

  • random access will work (although it's not clear what you expect the index to be once your vector is in heap order)
  • deleting an arbitrary element will require erasing it from the vector and re-running make_heap, or you can implement your own siftDown

Oh, and you can make some value type to store in your vector, such as

std::vector<std::pair<int,int>>

for your first example, or perhaps more clearly:

struct {
  int node;
  int weight;
} Node;
// ...
std::vector<Node>