In the C++ STL, the ordered set STL returns the minimum element in it on pop, so does the Prority queue STL when we include std::greater. also complexity of both of them are also same. Can we say that the ordered set and min heap priority queue are same in the STL? or any difference is there?
1 Like
No the priority_queue and set are not the same in STL. One important thing to note as far as set is concerned is that it only contains unique elements. It won’t allow you to store the duplicates. However storing duplicates is possible in prioriy_queue. Also if we have to find an element in a set it takes logarithmic time whereas same cannot be said for the priority queue. SO you can’t actually implement the decrease key operation required in Dijkstra’s algo using a prioriy queue because searching for the element would take too long . You can do the decrease key in O(log n) using a set but then NO DUPLICATES
Cheers !!
1 Like