Implementation of Prim's minimum spanning tree
Generally speaking, it seems to be coded pretty well. I can just find one or two things that could be improved:



else
{
    continue;
}


This piece of code at the end of a while seems fairly useless. I guess it would be the same without it.



void visitVertex(size_t index)
// helper method marks vertex as visited and adds all it's
// edges to priority queue
{
    visited.insert(index);
    for(size_t other : graph.getVertexNeighbors(index))
    {
        pq.push(EdgeWithPriority(index, other, graph));
    }
}


Here, you can replace pq.push(EdgeWithPriority(index, other, graph)); by pq.emplace(index, other, graph);. The function emplace will construct the object directly in the priority_queue with the given parameters.

You could also probably replace visited.insert(index); by visited.emplace(index); but I don't think it will change anything.



Graph* result = new Graph(impl-&gt;graph.verticesCount());
for(Graph::EdgeKey element : impl-&gt;edges)
{
    double weight = impl-&gt;graph.distance(element.first, element.second);
    result-&gt;connect(element.first, element.second, weight);
}


I don't know what the methods distance and connect do, but depending on what they really do, it could be better to for your for loop to take const references instead of values. But, well... it depends on distance and connect.



You should use std::unique_ptr instead of std::shared_ptr to hold the pointer to the implementation. Since std::unique_ptr cannot be copied, that means that PrimGraphMst cannot be copied either, but that's probably fine since std::shared_ptr was not copying your data either but merely doing an alias to the implementation.

You can also improve the constructor of PrimGraphMst by using a constructor initiaization list instead of a late memory allocation:

PrimGraphMst::PrimGraphMst(const Graph&amp; graph):
    impl{ new PrimGraphMstImplementation{graph} }
{}




You may have noted it: I used curly braces in the initialization list of the constructor in the previous section of this review. Contrary to plain parenthesis, curly braces prevent any implicit narrowing type conversion. Using them can help to catch the small errors that are sometimes linked to narrowing conversions.



Style: your indentation often seems off and makes the code quite difficult to review. You should indent your code evrytime you introduce a new scope.

You are placing the comments of your function right after their point of declaration. Generally speaking, comments about a function are placed right before the function declaration.