C#中的简单优先级队列 - 什么比使用自定义排序器的List更好:IComparer？

Question

我想实现一个优先级队列,它将注入我的对象 - Nodes相对于一个字段的队列 - f.我已经用自定义比较器编写了List,但这需要我:

• enqueue - 每次插入后对List进行排序

• dequeue - 删除最后一个(而不是第一个表现),如此

  myList.RemoveAt(myList.Count - 1);
  

我的列表应该总是根据某个字段排序(这里我需要它按照排序f).我还需要能够添加dequeue列表中具有最低值的对象.

有人能告诉我最好的办法是什么？

编辑

dasblinkenlight有一个非常好的答案,但我已经意识到我应该能够在这个容器中存储重复项.

Answer 1

如果您使用的是.NET 4或更高版本,则可以使用SortedSet<T>具有自定义的类IComparer<T>.

该类允许您使用Add所有可变集合通用的方法添加新对象.您可以使用Max属性检索max元素,然后调用Remove以从集合中删除max.

编辑:(响应编辑的问题)如果您需要存储重复项,您可以使用a SortedDictionary<Key,int>,并从中计算出一个计数集.同样,您可以选择使用自定义IComparer<T>.将元素排入队列时,检查它是否已存在,并增加其计数.出列时,再次检查计数,递减计数,并仅在计数达到零时移除密钥.

Answer 2

正如前面提到的，aSortedDictionary可以帮助您实现目标，您只需要一种处理重复优先级的方法。处理任何基于 Map 的结构（Dictionary、SortedDictionary等）中的重复项的方法是使值成为您真正想要的值的集合。在您的情况下，值是 a 最有意义Queue<T>。

这里是一个起点。如果需要Count，您可以添加其他方法，例如、 的实现IEnumerable等。

/// <summary>
/// 
/// </summary>
/// <typeparam name="TElement">The type of the actual elements that are stored</typeparam>
/// <typeparam name="TKey">The type of the priority.  It probably makes sense to be an int or long, \
/// but any type that can be the key of a SortedDictionary will do.</typeparam>
public class PriorityQueue<TElement, TKey>
{
    private SortedDictionary<TKey, Queue<TElement>> dictionary = new SortedDictionary<TKey, Queue<TElement>>();
    private Func<TElement, TKey> selector;


    public PriorityQueue(Func<TElement, TKey> selector)
    {
        this.selector = selector;
    }

    public void Enqueue(TElement item)
    {
        TKey key = selector(item);
        Queue<TElement> queue;
        if (!dictionary.TryGetValue(key, out queue))
        {
            queue = new Queue<TElement>();
            dictionary.Add(key, queue);
        }

        queue.Enqueue(item);
    }

    public TElement Dequeue()
    {
        if (dictionary.Count == 0)
            throw new Exception("No items to Dequeue:");
        var key = dictionary.Keys.First();

        var queue = dictionary[key];
        var output = queue.Dequeue();
        if (queue.Count == 0)
            dictionary.Remove(key);

        return output;
    }
}