Question prompted by a discussion elsewhere: If you were using a data structure named ‘PriorityQueue’, would you expect it to maintain FIFO ordering for values with the same priority?

Yes. But because priority should increase on items over time so it’s not possible to never do because of constant, higher priority items being added. So they really aren’t the same priority internally.

Ok, if we put aside priority aging, would you expect FIFO behaviour ? :slightly_smiling_face:

I would expect the behaviour to be documented - but both choices are valid.

Would not maintaining the ordering mean it isn’t a queue pretty much by definition, though?

Also, it is trivial to insert (object,counter) instead of just object, if you need it.

The priority queue needs more space if it needs to store a time counter.

In sorting, this behavior is called stable, fwiw

https://cstheory.stackexchange.com/questions/593/is-there-a-stable-heap\|https://cstheory.stackexchange.com/questions/593/is-there-a-stable-heap