What is the fastest (insert speed) way to achieve a prioritized collection of arrays in .Net?

Question

I am writing a specific priority queue. Its structure needs to be something as follows:

Priority(<int>)    Data(List<Object>)
1                  a, b, g, h
3                  c, d, j
4                  k
10                 e, f, i

I need to be able to efficiently find if a list exists for a given priority; if not, create the list and add the message, otherwise append the message to the existing list.

I have written a red-black tree, but this seems like overkill for this, and may not be the fastest solution. It also has the drawback of not being able to easily grab the messages by priority, which I need to be able to do once the writing has been completed.

I thought about Dictionary, but unless I am mistaken, it doesn't have a simple way to say "if the key __ exists, give me the value corresponding to it, otherwise give me null". Or am I missing something?

EDIT

My current implementation is to have 32 fixed lists. The applicable list is added to and the applicable bit set in a 32-bit flag. I use De Bruijn's algorithm to get the LSB. This is efficient, but is adding other complexity that I want to alleviate.

Answer 1

Maybe you should use Dictionary<int,List<object>>

public void Add(int priority,object data)
{
    if(dictionary.ContainsKey(priority))
       dictionary[priority].Add(data);
    else
       dictionary.Add(priority,new List<object>{data});
}

Answer 2

A SortedDictionary would fill the job. Just use TryGetValue() to conditionally find the list.

Answer 3

Hm, what's wrong with Dictionary as the underlying container? You get O(1) access/insertion time on average, instead of O(log n) with rb-trees. Just wrap Dictionary according to your needs, for example:

internal public class PriorityQueue<TValue> 
{
    private Dictionary<int, List<TValue>> mDict;

    // only Add, TryGetValue shown...
    public void Add(int pPriority, TValue pInput) 
    {
        List<TValue> tTmp;
        if (mDict.TryGetValue(pPriority, tTmp)) 
        {
            tTmp.Add(pInput);
        } 
        else 
        {
            mDict.Add(pPriority, new List<TValue>{ pInput });
        }
    }

    public bool TryGetValue(int pPriority, out List<TValue>) 
    {
        // obvious...
    }
}