Concurrent mutable priority queue

Question

Is there a concurrent mutable priority queue? Ideally, I'm looking for a C++ implementation, but, for starters, a pointer to an algorithm would be very helpful.

To be clear, I'm looking for a priority queue where I can adjust the priorities of the elements. In particular, TBB's concurrent_priority_queue doesn't provide the necessary functionality. (For that matter, neither does STL's priority_queue, even if we ignore the concurrency.) Boost.Heap library provides serial functionality that I want, but without concurrency. Naturally, I'm looking for something finer grained than just locking the entire queue on every operation.

Answer 1

A concurrent priority queue is often implemented using a skiplist, so Facebook's ConcurrentSkipList may fit your requirements.