A concurrent priority queue is a data structure linearizable to a sequential priority queue that provides insert and delete-min operations with the usual priority queue semantics. (See Part II of this handbook for more on sequential priority queues.)
Heap-Based Priority Queues
Many of the concurrent priority queue constructions in the literature are linearizable versions of the heap structures described earlier in this book. Again, the basic idea is to use ﬁne-grained locking of the individual heap nodes to allow threads accessing diﬀerent parts of the data structure to do so in parallel where possible. A key issue in designing such concurrent heaps is that traditionally insert operations proceed from the bottom up and delete-min operations from the top down, which creates potential for deadlock. Biswas and Brown  present such a lock-based heap algorithm assuming specialized “cleanup” threads to overcome deadlocks. Rao and Kumar  suggest to overcome the drawbacks of  using an algorithm that has both insert and delete-min operations proceed from the top down. Ayani  improved on their algorithm by suggesting a way to have consecutive insertions be performed on opposite sides of the heap. Jones  suggests a scheme similar to  based on a skew heap.
Hunt et al.  present a heap-based algorithm that overcomes many of the limitations of the above schemes, especially the need to acquire multiple locks along the traversal path in the heap. It proceeds by locking for a short duration a variable holding the size of the heap and a lock on either the ﬁrst or last element of the heap. In order to increase paral- lelism, insertions traverse the heap bottom-up while deletions proceed top-down, without introducing deadlocks. Insertions also employ a left-right technique as in  to allow them to access opposite sides on the heap and thus minimize interference.
On a diﬀerent note, Huang and Weihl  show a concurrent priority queue based on a concurrent version of Fibonacci Heaps .
Nonblocking linearizable heap-based priority queue algorithms have been proposed by Herlihy , Barnes , and Israeli and Rappoport . Sundell and Tsigas  present a lock-free priority queue based on a lock-free version of Pugh’s concurrent skiplist .
Tree-Based Priority Pools
Huang and Weihl  and Johnson  describe concurrent priority pools: priority queues with relaxed semantics that do not guarantee linearizability of the delete-min operations. Their designs are both based on a modiﬁed concurrent B+-tree implementation. Johnson introduces a “delete bin” that accumulates values to be deleted and thus reduces the load when performing concurrent delete-min operations. Shavit and Zemach  show a similar pool based on Pugh’s concurrent skiplist  with an added “delete bin” mechanism based on . Typically, the weaker pool semantics allows for increased concurrency. In  they further show that if the size of the set of allowable keys is bounded (as is often the case in operating systems) a priority pool based on a binary tree of combining funnel nodes can scale to hundreds (as opposed to tens) of processors.