Sorting in a Priority Queue
The definition of a priority queue is that elements will be dequeued in order of priority. The definition says nothing about the order of items of equal priority so an implementer can do anything, within reason, and still be justified in calling the resulting structure a priority queue.