7

オブジェクトを注入するプライオリティ キューを実装したいと思います - Nodes1 つのフィールドに関してキューに - f。私はすでにカスタム比較機能を使用してリストを作成しましたが、これには次のことが必要になります。

  • enqueue - 各挿入後にリストをソートします

  • dequeue - (パフォーマンスのために最初ではなく) 最後を削除します。

    myList.RemoveAt(myList.Count - 1);

私のリストは、常にいくつかのフィールドに従ってソートする必要があります（ここでは、 でソートする必要がありますf）。dequeueまた、リストから値が最も低いオブジェクトを追加する機能も必要です。

誰かがこれに対する最善のアプローチを教えてもらえますか?

編集

dasblinkenlightには非常に良い答えがありますが、このコンテナーに重複を保存できるはずであることに気付きました。

4

4 に答える 4

6

先に述べたように、aSortedDictionaryは途中までしか到達できません。重複した優先度を処理する方法が必要なだけです。DictionaryMap ベースの構造 ( 、など)で重複を処理する方法は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 に答える