7

我想实现一个优先级队列，它将我的对象注入Nodes到一个字段的队列中f。我已经用自定义比较器编写了列表，但这需要我：

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

  • dequeue - 像这样删除最后一个（而不是第一个以获得性能）

    myList.RemoveAt(myList.Count - 1);

我的列表应始终根据某个字段进行排序（这里我需要它按 排序f）。我还需要能够dequeue从列表中添加和具有最低值的对象。

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

编辑

dasblinkenlight有一个很好的答案，但我刚刚意识到我应该能够在这个容器中存储重复项。

4

4 回答 4

11

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

该类允许您使用Add所有可变集合共有的方法添加新对象。您可以使用该属性检索最大元素Max，然后调用Remove以从集合中删除最大值。

编辑：（响应问题的编辑）如果您需要存储重复项，您可以使用 a SortedDictionary<Key,int>，并从中进行计数。同样，您可以选择使用自定义IComparer<T>. 当你将一个元素加入队列时，检查它是否已经存在，并增加它的计数。出队时，再次检查计数，将其递减，只有当计数达到零时才移除密钥。

于 2012-12-20T22:17:24.873 回答
6

如前所述，aSortedDictionary让你分道扬镳，你只需要一种处理重复优先级的方法。Dictionary在任何基于 Map 的结构（ ,等）中处理重复项的方法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;
    }
}
于 2012-12-20T23:38:13.413 回答
0

.NET 6 现在有PriorityQueue<TElement,TPriority>：

var queue = new PriorityQueue<Foo, int>();
queue.Enqueue(new Foo("A"), 10);
queue.Enqueue(new Foo("B"), 15);
queue.Enqueue(new Foo("C"), -5);
queue.Enqueue(new Foo("D"), 1);

while (queue.TryDequeue(out var foo, out _))
{
    Console.WriteLine(foo.Name);
}

输出：

C
D
A
B

请注意，此实现不保证具有相同优先级的项目的顺序。

于 2021-11-16T10:00:44.930 回答
0

您也可以使用SortedSetwith 重复项。不是将值存储在集合中，而是存储列表的索引，然后在比较重复项时使用索引作为区分因素。

List<int> nums = new List<int>{1,2,1,3,3,2};
SortedSet<int> pq = new SortedSet<int>(Comparer<int>.Create(
    (x,y) => nums[x] != nums[y] ? nums[x]-nums[y] : x-y
));
    
for (int i=0; i<nums.Count; i++) pq.Add(i);
while (pq.Any())
{
    Console.Write(nums[pq.Min] + " ");
    pq.Remove(pq.Min);
}

https://dotnetfiddle.net/Egg3oN

编辑：

我重用了上面相同的代码来添加 OP 要求的两种方法

public static void Main()
{
    List<int> nums = new List<int>{1,2,1,3,3,2};
    SortedSet<int> pq = new SortedSet<int>(Comparer<int>.Create(
        (x,y) => nums[x] != nums[y] ? nums[x]-nums[y] : x-y
    ));
    
    for (int i=0; i<nums.Count; i++) Enqueue(pq, i);
    while (pq.Any())
    {
        int topIndex = Dequeue(pq);
        Console.Write(nums[topIndex] + " ");
    }
}

private static void Enqueue(SortedSet<int> pq, int numIndex)
{
    pq.Add(numIndex);
}

private static int Dequeue(SortedSet<int> pq)
{
    int topIndex = pq.Min;
    pq.Remove(pq.Min);
    return topIndex;
}
于 2021-02-07T19:41:01.030 回答