Skip to main content
gamedev.net
🔒 Locked

Stable Priority Queue

Started by Shannon Barber Jul 12, 2006 at 3:21 PM 2 replies 3.4k views
Original Post
Shannon Barber
Shannon Barber
I've been using a std::priority_queue to maintain the order of my task and I've come to a case where I want robin-round scheduling for equal priority task. Whenever a task is scheduled it is removed from the queue and re-added if it is to run again, so if the sort of the queue was stable this would result in round-robin scheduling. Problem is the priority queue use a heap (and heaps are not stable). I know there's stable_sort, but I don't want to completely resort the list when I add a node. Is there an insertion sort algorithm or something else I can use to create a stable priority queue?
The trade-off between price and quality does not exist in Japan. Rather, the idea that high quality brings on cost reduction is widely accepted.-- Tajima & Matsubara
deffer
deffer
I'm thinking:
std::multiset + insert with hint location taken from upper_bound

Don't know if it wil work as expected, or if at all, though.
Fruny
Fruny
Keep track of the insertion time (or order) and use it as a secondary key. That way, elements with equal priority will be kept in order of insertion time (or order).

Watch out for wraparound though.
"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." — Brian W. Kernighan
Trap
Trap
Bucket-based priority queues with queues for each bucket are stable.

Can you use a bucket-based queue in your app?

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.