So it is the same question as this(Inserting in a multiset: before the first occurence of that value instead of after the last occurence) but for a priority_queue. Also any insight on when to use what will be helpful.I see that priority_queue.push is O(log(n)) but pushing n elements is O(n). How is that possible?
In general, priority queues do not order equal-priority items based on arrival time. If you want to do that, you need to create your own comparison operator that compares not only the priority value but also the arrival time (or perhaps a monotonically increasing sequence number). The key here is that the priority queue itself doesn't care about insertion order.
For C++, see https://en.cppreference.com/w/cpp/container/priority_queue for more information about the priority queue and the Compare constructor parameter.
See Priority Queue remove items with same priority first one entered for an explanation of why, in a priority queue implemented as a binary heap, it's impossible to ensure that items of equal priority are removed in order (or reverse order) of insertion.
You said:
I see that priority_queue.push is O(log(n)) but pushing n elements is O(n). How is that possible?
It's not. You can't push n elements onto a heap in O(n) complexity. You can, however, turn an array of n elements into a heap in O(n) time. See How can building a heap be O(n) time complexity? for the details.