在 .Net 中实现数组优先集合的最快（插入速度）方法是什么？

Question

我正在写一个特定的优先级队列。它的结构需要如下所示：

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

我需要能够有效地查找给定优先级是否存在列表；如果没有，则创建列表并添加消息，否则将消息追加到现有列表中。

我写了一个红黑树，但这似乎有点矫枉过正，而且可能不是最快的解决方案。它还有一个缺点，就是无法轻松地按优先级抓取消息，而我需要在写入完成后才能做到这一点。

我想到了 Dictionary，但除非我弄错了，否则它没有一个简单的方法来表示“如果键 __ 存在，则给我对应的值，否则给我 null”。或者我错过了什么？

编辑

我当前的实现是有 32 个固定列表。将适用列表添加到 32 位标志中，并在 32 位标志中设置适用位。我使用 De Bruijn 算法来获取 LSB。这很有效，但增加了我想要减轻的其他复杂性。

Answer 1

也许你应该使用 Dictionary>

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

SortedDictionary 可以完成这项工作。只需使用 TryGetValue() 有条件地查找列表即可。

Answer 3

嗯，Dictionary 作为底层容器有什么问题吗？平均而言，您获得 O(1) 访问/插入时间，而不是 rb 树的 O(log n) 时间。只需根据您的需要包装 Dictionary 即可，例如：

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...
    }
}