[PriorityQueue] FIFO ordering

Related Projects Collections
1

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 Comparable implementation).

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?

1 Like
2

Thanks, will think a bit, but I think that should be the nail in the coffin for trying to use comparable in this context as previously discussed.

Having a requirement of hashable is much less fragile but Iā€™m a bit ponderous on always using side storage - would probably make sense to benchmark that against the overhead of storing the inline counters as previously discussed - not obvious how the time/space tradeoff looks like in practice.