Just some guy
Just some guy

Reputation: 1959

Java - Alternative to PriorityQueue that keeps duplicate insertion order

I have a problem where I need a data structure that let's me store a bunch of order objects (has price and quantity) in sorted order so that I can easily retrieve the one with the lowest price. The only operations I need are 'insert' and 'retrieve smallest' which makes a priority queue seems like a great choice, but the problem is that I also need to keep track of the insertion order of duplicates so that it's always the first inserted duplicate that gets retrieved first. Duplicates are just orders that have the same price in this case.

The Java PriorityQueue class seems to make no promises regarding the retrieval order of duplicates, so I need some other alternative. What would you guys recommend?

Upvotes: 2

Views: 1634

Answers (1)

Peter Lawrey
Peter Lawrey

Reputation: 533930

You can add a field or wrap the element with an atomic counter and/or timestamp to record the original order.

Upvotes: 6

Related Questions