C++ Priority Queue - Reorder based on updated priorities

Question

Some background: I am building a C++ thread manager which allows the user to create an AsyncJob object and assign a priority of execution. I have a JobManager singleton class which manages a priority queue of these AsyncJobs and assigns them to a thread when available.

The Problem: Users need to be able to modify the priority AFTER creation. For instance, based on some run-time events, a file may need to be loaded more urgently than others. The issue I am facing is that priority queues only reorder elements on the internal heap when push() or pop() is called. There is no exposed interface, to my knowledge, that allows one to request a reorder based on changing priorities.

What I would like to do is something like this:

• Create a hashmap in my JobManager class which holds pointers to objects in the priority queue
• User can access a requested job by its key and update the priority through the hash map
• The JobManager then signals to the priority queue that priorities have changed
• Priority queue reorders itself internally

What would be the best way of going about this? Should I expect to make my own custom priority queue class? Or maybe extend from the std::priority_queue?

Thanks!

Answer 1

One option could be to allow your AsyncJob to have a 'cancelled' state, and simply add a new (copy of) the AsyncJob to your PQ each time the priority is modified, after cancelling the old one.

As with many things, I'd suggest that 'best way' is highly subjective, as it depends on how constrained you are, and how you quantify 'best'. Personally I like to avoid deriving from standard library types and re-inventing container structures if possible.

Answer 2

A binary search tree seems like a decent alternative.

The binary search tree should be ordered by priority and, secondly, if priority isn't unique, a unique identifier / set of identifiers in the object.

If you don't know the previous priority when you want to change it, you'll need a way to look that up - perhaps a hash table of object to priority.

This allows you to remove and reinsert a specific item in O(log n), without losing the O(log n) performance on other operations (and O(1) to get the first).

---

For C++:

If priority is unique, a map of priority to object could work, otherwise a set<pair> where the first element in the pair is the priority, and the second is the object (yes, I know, those aren't necessarily BST's).

For the hash table, you could use an unordered_map of object to priority, or simply a map pre-C++11.