On: Multithreaded data structures for parallel computi...

[pjscott]

And for priority queues, there's a wonderfully clever scheme which involves using a skiplist:

http://www-cs-students.stanford.edu/~itayl/ipdps.pdf

The probabilistic nature of the data structure lets them get those nice O(lg n) and O(1) expected times without the wide-ranging memory conflicts that slow down concurrent min-heaps. Some more basic info on skiplists for people who aren't familiar with them:

http://en.wikipedia.org/wiki/Skip_list

[marshray → pjscott]

Yes I'm working on an implementation of those myself.

There are even designs for lock-free skiplist priorty queues, but they tend to be a little slower than the locking versions.

[pjscott → marshray]

Lock-free skiplist priority queues, incidentally, become very elegant if your processor supports even the most basic hardware transactional memory.