We recently discovered in our upstream implementation of
PriorityQueue (similar in shape to that proposed in this PR) that it only respects FIFO ordering when dequeueing the minimum element but not when dequeuing the maximum (due to the
I added a comment to that PR with a potential way to properly support this (only store the priorities in the heap and use a separate storage for the elements that supports ordering (i.e. a linked list or a deque)).
Does anyone have thoughts on this? What are the other approaches are for maintaining FIFO ordering in a priority queue?