Does a sorted queue exist in .NET?

Question

I have a need for a fairly specialised collection .NET, and I don't think that the BCL can help me, but I thought I'd throw it out there for if anyone knew of something similar.

Basically, my requirements are thus:

• I have a list of pairs of values, such as: (3, 10), (5, 10), (3, 7), (5, 5)
• Order is important, ie. (3, 10) != (10, 3)
• Duplicates of individual values are fine, but duplicate pairs should be dropped (preferably silently).
• The kicker is, I need this list sorted all the time. I'm only ever interested in the first value in the list as defined by the sort algorithm at any one time.

So, some example code of what I want to be able to do (as I envision it would probably be implemented, other implementations that fit the above are fine to):

public class Pair
{
    public Pair(int first, int second)
    { First = first; Second = second; }
    public int First { get; set; }
    public int Second { get; set; }
}

SortedQueue<Pair> foo = new SortedQueue<Pair>((left, right) => {
    return right.First - left.First;
});

foo.Add(new Pair(10, 3));
foo.Add(new Pair(4, 6));
foo.Add(new Pair(6, 15));
foo.Add(new Pair(6, 13)); // This shouldn't cause a problem

Pair current = foo.Shift(); // current = (4, 6)

Answer 1

I quote:

I need this list sorted all the time. I'm only ever interested in the first value in the list as defined by the sort algorithm at any one time.

This sounds like you do not want a Sorted Queue but a Priority Queue. If performance is an issue then a PQ will certainly be faster, O(log n) vs O(n). But the drop-duplicates issue would require you to keep a parallel HashSet<> as well.

Answer 2

Have you looked at SortedDictionary or SortedList?

Answer 3

Check out the C5 Generic Collections Library which already has an implementation just like you're looking for, called an IntervalHeap or Priority Queue. Here's some documentation on it from the C5 Book: IPriorityQueue<T>

Answer 4

There is nothing built into .NET at this time that meets all of your requirements. In .NET 4.0 there is a SortedSet class. I realize that it probably does not do you much good now.

SortedList comes close if you implement IComparable. You would just use the Pair as the key and the value. You would only be storing the reference to your Pair twice so it isn't a huge memory overhead. But this will not take care of duplicates.

There are numerous ways to write it yourself, but nothing built in that fully matches what you need. There are a few open source SortedSet implementations (there is one in Spring.Net for example). That might be your best bet right now.