I have a priority queue (using a max heap) that preserves insertion order for duplicate priorities, such that equal priorities fall back to FIFO behaviour. I'm doing this by creating a node with the value, the priority, and an 'insertion stamp' that is basically an incrementing number on the structure. I'd like to remove the need for this stamp, but I'm not sure if it's possible.
How might this work?
That's a perfectly reasonable approach. Use (priority, insertion timestamp) as the priority value for your heap, with comparisons using lexicographic order (compare by priority, breaking ties by insertion timestamp). That's all simple and easy to implement, and has no downsides that I can see.
Alternative, you can have one node in the priority queue per priority, with a pointer to a queue of items with that priority. That also works and is easy to implement.
