0
$\begingroup$

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?

Improve this question
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I was hoping to avoid the insertion timestamp, maybe by following a policy when constructing the heap such that relative ordering is preserved. $\endgroup$ – rtheunissen May 25 '18 at 9:56
  • $\begingroup$ @rtheunissen, I don't understand why (the insertion timestamp is a way to ensure that relative ordering is preserved), but in any case, if that's your goal, see the second paragraph of my answer, which describes a way to achieve that. $\endgroup$ – D.W.♦ May 25 '18 at 15:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.