Wouldn't this be better implemented using a standard priority queue where the score is related to the timestamp of insertion?
A queue is fundamentally wrong for this type of use case.
This is a valid min-heap: (5 ((7 (9, 10)), (8 (11, 12)))). Where in (a (b, c)) b and c are children of a. If you want to peek(5) you have to:
1. peek 5
2. peek the min of 7 and 8 (7)
3. now you have to peek the min of 9, 10 and 8.
4. it's 8, now you have to peek the min of 9,10,11 and 12
The thing is, the only guarantee you have is that a root node of a tree or subtree is smaller than its children. You know nothing of a sibling subtree.
I think maintaining a simple list is the simplest way of doing that, and to speed up lookups for existing items, an index (map item->index) can be maintained. Or the other way around, keep the objects in a map and the keys in the order list. Considering a size n=5 it might even be reasonable to do everything with a simple array and iterate over it.
See here for a very good writeup of priority queues and variants. http://algs4.cs.princeton.edu/24pq/
(not hugely familiar with Java so this stuff might be wrong) The implementation presented has some bad timing issues (List.Contains is a linear search). I think List.Remove is also a linear search. As well this implementation doesn't seem to do Point (1).