I was trying to implement Prim's algorithm using min Heap. here is the link I was referring to https://www.geeksforgeeks.org/prims-mst-for-adjacency-list-representation-greedy-algo-6/
I was wondering why can we use a vector and sort it using std::sort
function in place of min heap.
You could, but remember that every time a new node is added to the MST you have to update the set of edges that cross the partition (edges to nodes that are not yet in the MST), so you would have to sort your vector at every iteration of the algorithm, which would waste time, since you just need to know which of the edges that cross the partition has the minimum value at that iteration, the min-heap is optimal for that operation since its time complexity for extracting the minimum value is O(log n)
while the sort is O(n log n)
which can make the algorithm run slower on large or dense graphs.