Concurrent Priority Queue (Skiplist-Based)

When a concurrent priority queue is needed

A priority queue lets a producer hand work to a consumer with the consumer always picking the highest-priority item next. The cases that need it tend to be a small set:

• A job scheduler that runs higher-priority jobs first.
• An event-driven simulator that processes events in timestamp order.
• A network packet scheduler that drains high-priority queues first.
• A database query optimiser that processes its lowest-cost candidate plan first.

For most of these, Java's PriorityBlockingQueue is enough. It is a binary heap behind a single lock, well-tested and predictable. Only reach for a lock-free skiplist-backed design after measurement shows the heap's lock is the actual bottleneck. Lock-free priority queues are not free; the skiplist uses several times more memory than a heap and has worse cache locality.

The skiplist, in a picture

A skiplist is a sorted linked list with express lanes stacked on top of it. The bottom level (level 0) contains every item in sorted order. Each higher level contains a random half of the level below it. The result is a structure that has the same O(log n) search cost as a balanced tree, but with much simpler concurrent updates.

H is the head sentinel. The same physical key (for example 50) is referenced once per level it appears in; the diagram shows one node per occurrence to keep the picture readable.

Searching for 35 takes the express lanes first and drops to the local roads at the end:

The total number of comparisons is roughly log₂(N), the same as a balanced tree, because every level halves the search space.

Inserting picks a random level for the new node (50% chance of just level 1, 25% chance of level 2, 12.5% of level 3, and so on), then splices the new node into every level it appears in. Pop-min reads the first real node at level 0.

The reason this works as a lock-free design: inserts are local. The only pointers that change are the ones in the new node and its predecessors at each level it occupies. There is no global rebalance like a red-black tree would need. Each level's splice is a single CAS (compare the predecessor's next pointer, swap it to the new node), which is exactly the operation a lock-free retry loop is built around.

Java's ConcurrentSkipListMap

Java's ConcurrentSkipListMap is the production-grade implementation of this idea. The properties that matter:

• Reads are lock-free. Traversal walks the levels with plain atomic loads. Concurrent inserts do not block readers.
• Inserts and deletes are CAS-based at each level the node touches. No lock acquisition.
• Average cost is O(log n) for get, put, and remove, the same as a balanced tree.
• Iterators are weakly consistent. They never throw ConcurrentModificationException, but they may or may not reflect concurrent updates that happen during the iteration.
• Memory overhead is real. Around four times the memory of a TreeMap for the same number of entries, because every node needs a pointer per level and the multi-level structure has empty slots.

For a priority queue, the idiomatic shape is a ConcurrentSkipListMap<Integer, ConcurrentLinkedQueue<Task>>. The outer map is sorted by priority; the inner queue holds all tasks at that priority in FIFO order. firstEntry() reads the highest-priority bucket, poll() on its queue takes the oldest task at that priority, and an empty bucket gets cleaned up with a race-tolerant remove.