Concurrent Priority Queue in .NET 4.0

There is an implementation as part of "Samples for Parallel Programming with the .NET Framework" at msdn. See ParallelExtensionsExtras.

Direct link to source code for file ConcurrentPriorityQueue.cs

Recently, I was creating a state machine in which I needed time-stamped events. Rather than just a simple clock tick, I needed timed events with their own IDs so that I could distinguish one event from another.

Researching this problem led me to the idea of using a priority queue. I could en-queue the timed events along with their information in any order; the priority queue would take care of ordering the events properly. A timer would periodically check the priority queue to see if it is time for the event at the head of the queue to fire. If so, it de-queues the event and invokes the delegate associated with it. This approach was exactly what I was looking for.

Searching here at CodeProject

https://www.codeproject.com/Articles/13295/A-Priority-Queue-in-C

I found that a priority queue[^] class had already been written. However, it occurred to me that I could easily write my own using my old friend, the skip list. This would have the advantage that the de-queue operation would only take O(1) time, while the en-queue operation would still be log(n) on average. I thought that using skip lists in this way was novel enough that it merits its own article.

So here it is. I hope you find it interesting.

I've found a great example of a concurrent priority queue here. Hope it will help you a little.

var priorityQueue = new ConcurrentPriorityQueue<TKey, TValue>();

TKey in the context of this queue could be an int value or any other object that implements IComparable.

For consuming such a queue you may do a following:

var priorityQueue = new ConcurrentPriorityQueue<int, object>(); 

// Add elements
priorityQueue.Enqueue(2, elementP2); 
priorityQueue.Enqueue(1, elementP1);

// Here you will receive elementP1
bool result = priorityQueue.TryDequeue(out KeyValuePair<int, object> element);