This class seems missing from java.util.concurrent to me, so I've written an implementation. I'd imagine that it'd be easy to retrofit java.util.concurrent.PriorityBlockingQueue with the part necessary to make it work too.