Thread-safe Priority Queue for Delphi?

Question

I'm looking for a priority queue implemented in Delphi that would work well in a multi-threaded environment.

Ideally lock-free, or designed for multi-threaded inserts/deletes with something better than a locked wrapper around a single-threaded implementation (which I already have).

The specificity is that in normal operation, there would be only adds, deletes, and notifications when the top (highest priority item) changes, while "pop" operations of the highest priority item should be very infrequent.

It would be used for a watchdog/timeout thread monitoring tasks, being executed in other threads, those task are expected to terminate normally most of the time, so they would just be added/removed from the queue. The timeout thread would essentially be waiting on the next timeout event, hence the need for notifications when the top-priority event changes.

The tasks are handled by scripts, which can be safely terminated at any time.

If there are better algorithms for this than a priority queue, they could be good answers too!

Edit: following a remark by Martin James, another specificity is that there are relatively few different timeout values, and for each timeout value, the problem becomes that of a FIFO queue.

Answer 1

Julian Bucknall (Author of "Tomes of Delphi: Algorithms and Data Structures" ) has recently announced the release of a Delphi XE version of EZDSL(a Delphi Structures Library) in his Blog.

Unfortunately TThreadsafePriorityQueue (implemented in EZDSLPQu.PAS) is lock based.

I can't help sharing the good news and my other intent is a call for his contribution in answering the question.