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?