Prioritätswarteschlange in .Net [geschlossen]

216

Ich suche nach einer .NET-Implementierung einer Prioritätswarteschlange oder einer Heap-Datenstruktur

Prioritätswarteschlangen sind Datenstrukturen, die mehr Flexibilität bieten als einfaches Sortieren, da sie es neuen Elementen ermöglichen, in beliebigen Intervallen in ein System einzutreten. Es ist viel kostengünstiger, einen neuen Job in eine Prioritätswarteschlange einzufügen, als bei jeder Ankunft alles neu zu sortieren.

Die Warteschlange mit grundlegender Priorität unterstützt drei primäre Vorgänge:

  • Einfügen (Q, x). Fügen Sie ein Element x mit dem Schlüssel k in die Prioritätswarteschlange Q ein.
  • Find-Minimum (Q). Geben Sie einen Zeiger auf das Element zurück, dessen Schlüsselwert kleiner als jeder andere Schlüssel in der Prioritätswarteschlange Q ist.
  • Delete-Minimum (Q). Entfernen Sie das Element aus der Prioritätswarteschlange Q, dessen Schlüssel minimal ist

Wenn ich nicht am falschen Ort suche, gibt es keinen im Rahmen. Ist jemandem ein guter bekannt, oder sollte ich meinen eigenen rollen?

Doug McClean
quelle
34
Zu Ihrer Information Ich habe eine benutzerfreundliche, hochoptimierte C # -Prioritätswarteschlange entwickelt, die hier zu finden ist . Es wurde speziell für Pfadfindungsanwendungen (A * usw.) entwickelt, sollte aber auch für jede andere Anwendung perfekt funktionieren. Ich würde dies als Antwort posten, aber die Frage wurde vor kurzem geschlossen ...
BlueRaja - Danny Pflughoeft
1
ParallelExtensionsExtras hat einen ConcurrentPriorityQueue code.msdn.microsoft.com/ParExtSamples
VoteCoffee
Führen Sie PriorityQueue schamlos ein , um die gleichzeitige Java-API für Spring.Net auf .net zu portieren. Es ist sowohl ein Haufen als auch eine Warteschlange mit vollständiger generischer Unterstützung. Binär kann hier heruntergeladen werden .
Kenneth Xu
@ BlueRaja-DannyPflughoeft Könntest du dem eine Antwort hinzufügen?
Mafu
1
Nur um es zusammenzufassen. Es gibt keine Heap-Datenstruktur in .net und auch nicht im .net-Kern. Obwohl Array.Sort es für große Zahlen verwendet. Interne Implementierungen existieren.
Artyom

Antworten:

44

Ich verwende gerne die Klassen OrderedBagund OrderedSetin PowerCollections als Prioritätswarteschlangen.

Ben Hoffstein
quelle
60
OrderedBag / OrderedSet erledigen mehr Arbeit als nötig, sie verwenden einen rot-schwarzen Baum anstelle eines Haufens.
Dan Berindei
3
@ DanBerindei: keine notwendige Arbeit, wenn Sie eine laufende Berechnung durchführen müssen (alte Elemente löschen), Heap unterstützt nur das Löschen von Min oder Max
Svisstack
69

Möglicherweise gefällt Ihnen IntervalHeap aus der C5 Generic Collection Library . Um das Benutzerhandbuch zu zitieren

Die Klasse IntervalHeap<T>implementiert die Schnittstelle IPriorityQueue<T>mithilfe eines Intervall-Heaps, der als Array von Paaren gespeichert ist. Die Operationen FindMin und FindMax sowie der Get-Accessor des Indexers benötigen Zeit O (1). Die Operationen DeleteMin, DeleteMax, Add and Update und der Set-Accessor des Indexers benötigen Zeit O (log n). Im Gegensatz zu einer normalen Prioritätswarteschlange bietet ein Intervallheap sowohl minimale als auch maximale Operationen mit derselben Effizienz.

Die API ist einfach genug

> var heap = new C5.IntervalHeap<int>();
> heap.Add(10);
> heap.Add(5);
> heap.FindMin();
5

Installieren Sie von Nuget https://www.nuget.org/packages/C5 oder GitHub https://github.com/sestoft/C5/

Jaras
quelle
3
Dies scheint eine sehr solide Bibliothek zu sein, die 1400 Unit-Tests enthält.
ECC-Dan
2
Ich habe versucht, es zu benutzen, aber es hat schwerwiegende Mängel. IntervalHeap verfügt nicht über ein integriertes Prioritätskonzept und zwingt Sie, IComparable oder IComparer zu implementieren, sodass es eine sortierte Sammlung und keine "Priorität" ist. Schlimmer noch, es gibt keine direkte Möglichkeit, die Priorität eines vorherigen Eintrags zu aktualisieren !!!
Morteza Khosravi
52

Hier ist mein Versuch, einen .NET-Heap zu erstellen

public abstract class Heap<T> : IEnumerable<T>
{
    private const int InitialCapacity = 0;
    private const int GrowFactor = 2;
    private const int MinGrow = 1;

    private int _capacity = InitialCapacity;
    private T[] _heap = new T[InitialCapacity];
    private int _tail = 0;

    public int Count { get { return _tail; } }
    public int Capacity { get { return _capacity; } }

    protected Comparer<T> Comparer { get; private set; }
    protected abstract bool Dominates(T x, T y);

    protected Heap() : this(Comparer<T>.Default)
    {
    }

    protected Heap(Comparer<T> comparer) : this(Enumerable.Empty<T>(), comparer)
    {
    }

    protected Heap(IEnumerable<T> collection)
        : this(collection, Comparer<T>.Default)
    {
    }

    protected Heap(IEnumerable<T> collection, Comparer<T> comparer)
    {
        if (collection == null) throw new ArgumentNullException("collection");
        if (comparer == null) throw new ArgumentNullException("comparer");

        Comparer = comparer;

        foreach (var item in collection)
        {
            if (Count == Capacity)
                Grow();

            _heap[_tail++] = item;
        }

        for (int i = Parent(_tail - 1); i >= 0; i--)
            BubbleDown(i);
    }

    public void Add(T item)
    {
        if (Count == Capacity)
            Grow();

        _heap[_tail++] = item;
        BubbleUp(_tail - 1);
    }

    private void BubbleUp(int i)
    {
        if (i == 0 || Dominates(_heap[Parent(i)], _heap[i])) 
            return; //correct domination (or root)

        Swap(i, Parent(i));
        BubbleUp(Parent(i));
    }

    public T GetMin()
    {
        if (Count == 0) throw new InvalidOperationException("Heap is empty");
        return _heap[0];
    }

    public T ExtractDominating()
    {
        if (Count == 0) throw new InvalidOperationException("Heap is empty");
        T ret = _heap[0];
        _tail--;
        Swap(_tail, 0);
        BubbleDown(0);
        return ret;
    }

    private void BubbleDown(int i)
    {
        int dominatingNode = Dominating(i);
        if (dominatingNode == i) return;
        Swap(i, dominatingNode);
        BubbleDown(dominatingNode);
    }

    private int Dominating(int i)
    {
        int dominatingNode = i;
        dominatingNode = GetDominating(YoungChild(i), dominatingNode);
        dominatingNode = GetDominating(OldChild(i), dominatingNode);

        return dominatingNode;
    }

    private int GetDominating(int newNode, int dominatingNode)
    {
        if (newNode < _tail && !Dominates(_heap[dominatingNode], _heap[newNode]))
            return newNode;
        else
            return dominatingNode;
    }

    private void Swap(int i, int j)
    {
        T tmp = _heap[i];
        _heap[i] = _heap[j];
        _heap[j] = tmp;
    }

    private static int Parent(int i)
    {
        return (i + 1)/2 - 1;
    }

    private static int YoungChild(int i)
    {
        return (i + 1)*2 - 1;
    }

    private static int OldChild(int i)
    {
        return YoungChild(i) + 1;
    }

    private void Grow()
    {
        int newCapacity = _capacity*GrowFactor + MinGrow;
        var newHeap = new T[newCapacity];
        Array.Copy(_heap, newHeap, _capacity);
        _heap = newHeap;
        _capacity = newCapacity;
    }

    public IEnumerator<T> GetEnumerator()
    {
        return _heap.Take(Count).GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

public class MaxHeap<T> : Heap<T>
{
    public MaxHeap()
        : this(Comparer<T>.Default)
    {
    }

    public MaxHeap(Comparer<T> comparer)
        : base(comparer)
    {
    }

    public MaxHeap(IEnumerable<T> collection, Comparer<T> comparer)
        : base(collection, comparer)
    {
    }

    public MaxHeap(IEnumerable<T> collection) : base(collection)
    {
    }

    protected override bool Dominates(T x, T y)
    {
        return Comparer.Compare(x, y) >= 0;
    }
}

public class MinHeap<T> : Heap<T>
{
    public MinHeap()
        : this(Comparer<T>.Default)
    {
    }

    public MinHeap(Comparer<T> comparer)
        : base(comparer)
    {
    }

    public MinHeap(IEnumerable<T> collection) : base(collection)
    {
    }

    public MinHeap(IEnumerable<T> collection, Comparer<T> comparer)
        : base(collection, comparer)
    {
    }

    protected override bool Dominates(T x, T y)
    {
        return Comparer.Compare(x, y) <= 0;
    }
}

Einige Tests:

[TestClass]
public class HeapTests
{
    [TestMethod]
    public void TestHeapBySorting()
    {
        var minHeap = new MinHeap<int>(new[] {9, 8, 4, 1, 6, 2, 7, 4, 1, 2});
        AssertHeapSort(minHeap, minHeap.OrderBy(i => i).ToArray());

        minHeap = new MinHeap<int> { 7, 5, 1, 6, 3, 2, 4, 1, 2, 1, 3, 4, 7 };
        AssertHeapSort(minHeap, minHeap.OrderBy(i => i).ToArray());

        var maxHeap = new MaxHeap<int>(new[] {1, 5, 3, 2, 7, 56, 3, 1, 23, 5, 2, 1});
        AssertHeapSort(maxHeap, maxHeap.OrderBy(d => -d).ToArray());

        maxHeap = new MaxHeap<int> {2, 6, 1, 3, 56, 1, 4, 7, 8, 23, 4, 5, 7, 34, 1, 4};
        AssertHeapSort(maxHeap, maxHeap.OrderBy(d => -d).ToArray());
    }

    private static void AssertHeapSort(Heap<int> heap, IEnumerable<int> expected)
    {
        var sorted = new List<int>();
        while (heap.Count > 0)
            sorted.Add(heap.ExtractDominating());

        Assert.IsTrue(sorted.SequenceEqual(expected));
    }
}
Ohad Schneider
quelle
2
Ich würde empfehlen, den Heap-Wert in ExtractDominating zu löschen, damit das referenzierte Objekt nicht länger als nötig erhalten bleibt (potenzieller Speicherverlust). Für Werttypen ist dies offensichtlich nicht von Belang.
Wout
5
Schön, aber Sie können keine Gegenstände daraus entfernen? Dies ist eine wichtige Operation für Prioritätswarteschlangen.
Tom Larkworthy
Es sieht so aus, als wäre das zugrunde liegende Objekt ein Array. Wäre das nicht besser als Binärbaum?
Grunion Shaftoe
1
@OhadSchneider sehr, sehr cool, ich habe mich nur mit Min Heap befasst und versucht, das zu tun, was du getan hast, um es generisch und Min oder Max Heap zu machen! großartige Arbeit
Gilad
1
@Gilad IEqualityComparer<T>würde nicht ausreichen, da dies nur Aufschluss darüber gibt, ob zwei Elemente gleich sind, während Sie die Beziehung zwischen ihnen kennen müssen (wer ist kleiner / größer). Es ist wahr, dass ich hätte verwenden können IComparer<T>...
Ohad Schneider
23

Hier ist eine, die ich gerade geschrieben habe. Vielleicht ist sie nicht so optimiert (verwendet nur ein sortiertes Wörterbuch), aber einfach zu verstehen. Sie können Objekte verschiedener Art einfügen, also keine generischen Warteschlangen.

using System;
using System.Diagnostics;
using System.Collections;
using System.Collections.Generic;

namespace PrioQueue
{
    public class PrioQueue
    {
        int total_size;
        SortedDictionary<int, Queue> storage;

        public PrioQueue ()
        {
            this.storage = new SortedDictionary<int, Queue> ();
            this.total_size = 0;
        }

        public bool IsEmpty ()
        {
            return (total_size == 0);
        }

        public object Dequeue ()
        {
            if (IsEmpty ()) {
                throw new Exception ("Please check that priorityQueue is not empty before dequeing");
            } else
                foreach (Queue q in storage.Values) {
                    // we use a sorted dictionary
                    if (q.Count > 0) {
                        total_size--;
                        return q.Dequeue ();
                    }
                }

                Debug.Assert(false,"not supposed to reach here. problem with changing total_size");

                return null; // not supposed to reach here.
        }

        // same as above, except for peek.

        public object Peek ()
        {
            if (IsEmpty ())
                throw new Exception ("Please check that priorityQueue is not empty before peeking");
            else
                foreach (Queue q in storage.Values) {
                    if (q.Count > 0)
                        return q.Peek ();
                }

                Debug.Assert(false,"not supposed to reach here. problem with changing total_size");

                return null; // not supposed to reach here.
        }

        public object Dequeue (int prio)
        {
            total_size--;
            return storage[prio].Dequeue ();
        }

        public void Enqueue (object item, int prio)
        {
            if (!storage.ContainsKey (prio)) {
                storage.Add (prio, new Queue ());
              }
            storage[prio].Enqueue (item);
            total_size++;

        }
    }
}
kobi7
quelle
Dies erlaubt jedoch nicht mehrere Einträge mit derselben Priorität?
Letseatlunch
2
es tut. Wenn Sie die Enqueue-Methode aufrufen, wird das Element zur Warteschlange mit dieser Priorität hinzugefügt. (der Teil in sonst in der Enqueue-Methode.)
Kobi7
5
Was meinst du mit "es ist nicht wirklich eine Prioritätswarteschlange in der Bedeutung der Informatik"? Was lässt Sie glauben, dass dies keine Prioritätswarteschlange ist?
Mark Byers
13
-1 für die Nichtverwendung von Generika.
Cdiggins
2
Einer der größten Vorteile von Heap / PriorityQueue ist die O (1) -Komplexität der Min / Max-Extraktion, dh die Peek-Operation. Und hier geht es um Enumerator-Setup, For-Loop usw. Warum!? Außerdem hat die Operation "Enqueue" anstelle von O (logN) - ein weiteres wichtiges Merkmal des Heaps - einen O (longN) -Wisch aufgrund von "ContainsKey", einen zweiten (erneut O (longN)), um den Warteschlangeneintrag hinzuzufügen (falls erforderlich), eine dritte, um die Warteschlange (die Speicherzeile [prio]) tatsächlich abzurufen, und schließlich eine lineare Hinzufügung zu dieser Warteschlange. Dies ist angesichts der Implementierung des Kernalgorithmus wirklich verrückt.
Jonan Georgiev
9

Wie in Microsoft Collections for .NET erwähnt , hat Microsoft zwei interne PriorityQueue-Klassen geschrieben (und online freigegeben) in .NET Framework . Ihr Code steht zum Ausprobieren zur Verfügung.

BEARBEITEN: Wie @ mathusum-mut kommentierte, gibt es einen Fehler in einer der internen PriorityQueue-Klassen von Microsoft (die SO-Community hat natürlich Korrekturen dafür bereitgestellt): Fehler in der internen PriorityQueue <T> von Microsoft?

Wehr
quelle
10
Ein Fehler wurde in einer der Implementierungen hier gefunden: stackoverflow.com/questions/44221454/…
MathuSum Mut
ohh! Ich kann sehen, dass alle diese Klassen PriorityQueue<T>in der gemeinsam genutzten Quelle von Microsoft mit einem internalZugriffsspezifizierer gekennzeichnet sind . Sie werden also nur von den internen Funktionen des Frameworks verwendet. Sie sind nicht für den allgemeinen Verbrauch verfügbar, wenn Sie nur auf windowsbase.dllein C # -Projekt verweisen . Die einzige Möglichkeit besteht darin, die freigegebene Quelle innerhalb einer Klassendatei in das Projekt selbst zu kopieren.
RBT
7
class PriorityQueue<T>
{
    IComparer<T> comparer;
    T[] heap;
    public int Count { get; private set; }
    public PriorityQueue() : this(null) { }
    public PriorityQueue(int capacity) : this(capacity, null) { }
    public PriorityQueue(IComparer<T> comparer) : this(16, comparer) { }
    public PriorityQueue(int capacity, IComparer<T> comparer)
    {
        this.comparer = (comparer == null) ? Comparer<T>.Default : comparer;
        this.heap = new T[capacity];
    }
    public void push(T v)
    {
        if (Count >= heap.Length) Array.Resize(ref heap, Count * 2);
        heap[Count] = v;
        SiftUp(Count++);
    }
    public T pop()
    {
        var v = top();
        heap[0] = heap[--Count];
        if (Count > 0) SiftDown(0);
        return v;
    }
    public T top()
    {
        if (Count > 0) return heap[0];
        throw new InvalidOperationException("优先队列为空");
    }
    void SiftUp(int n)
    {
        var v = heap[n];
        for (var n2 = n / 2; n > 0 && comparer.Compare(v, heap[n2]) > 0; n = n2, n2 /= 2) heap[n] = heap[n2];
        heap[n] = v;
    }
    void SiftDown(int n)
    {
        var v = heap[n];
        for (var n2 = n * 2; n2 < Count; n = n2, n2 *= 2)
        {
            if (n2 + 1 < Count && comparer.Compare(heap[n2 + 1], heap[n2]) > 0) n2++;
            if (comparer.Compare(v, heap[n2]) >= 0) break;
            heap[n] = heap[n2];
        }
        heap[n] = v;
    }
}

einfach.

Shimou Dong
quelle
13
Manchmal sehe ich for (var n2 = n / 2; n > 0 && comparer.Compare(v, heap[n2]) > 0; n = n2, n2 /= 2) heap[n] = heap[n2];
1
@DustinBreakey persönlicher Stil :)
Shimou Dong
3
aber definitiv nicht für andere lesbar. Schreiben Sie Code, bei dem kein Fragezeichen auf dem Kopf des Entwicklers schwebt.
Azaimar
3

Verwenden Sie einen Java to C # -Übersetzer für die Java-Implementierung (java.util.PriorityQueue) im Java Collections-Framework oder verwenden Sie den Algorithmus und den Kerncode intelligenter und fügen Sie ihn in eine eigene C # -Klasse ein, die dem C # Collections-Framework entspricht API für Warteschlangen oder zumindest Sammlungen.

JeeBee
quelle
Dies funktioniert, aber leider unterstützt IKVM keine Java-Generika, sodass Sie die Typensicherheit verlieren.
Mechanische Schnecke
8
Es gibt keine "Java-Generika", wenn Sie mit kompiliertem Java-Bytecode arbeiten. IKVM kann das nicht unterstützen.
Mark
3

AlgoKit

Ich habe eine Open-Source-Bibliothek namens AlgoKit geschrieben , die über NuGet verfügbar ist . Es beinhaltet:

  • Implizite D- Ary -Heaps (ArrayHeap),
  • Binomialhaufen ,
  • Haufen von Paaren .

Der Code wurde ausgiebig getestet. Ich empfehle Ihnen auf jeden Fall, es zu versuchen.

Beispiel

var comparer = Comparer<int>.Default;
var heap = new PairingHeap<int, string>(comparer);

heap.Add(3, "your");
heap.Add(5, "of");
heap.Add(7, "disturbing.");
heap.Add(2, "find");
heap.Add(1, "I");
heap.Add(6, "faith");
heap.Add(4, "lack");

while (!heap.IsEmpty)
    Console.WriteLine(heap.Pop().Value);

Warum diese drei Haufen?

Die optimale Wahl der Implementierung hängt stark von der Eingabe ab - wie Larkin, Sen und Tarjan in einer empirischen Studie zu Prioritätswarteschlangen zeigen , arXiv: 1403.0252v1 [cs.DS] . Sie testeten implizite D-Ary-Heaps, Pairing-Heaps, Fibonacci-Heaps, Binomial-Heaps, explizite D-Ary-Heaps, Rang-Pairing-Heaps, Beben-Heaps, Verstoß-Heaps, rangentspannte schwache Heaps und strenge Fibonacci-Heaps.

AlgoKit bietet drei Arten von Haufen, die unter den getesteten am effizientesten zu sein schienen.

Tipp zur Wahl

Für eine relativ kleine Anzahl von Elementen wären Sie wahrscheinlich daran interessiert, implizite Heaps zu verwenden, insbesondere quaternäre Heaps (implizite 4-Ary). Bei größeren Heap-Größen sollten amortisierte Strukturen wie Binomial-Heaps und Pairing-Heaps eine bessere Leistung erzielen.

Patryk Gołębiowski
quelle
1

Ich hatte kürzlich das gleiche Problem und habe schließlich ein NuGet-Paket dafür erstellt.

Dies implementiert eine standardmäßige Heap-basierte Prioritätswarteschlange. Es hat auch alle üblichen Besonderheiten der BCL-Sammlungen: ICollection<T>und IReadOnlyCollection<T>Implementierung, benutzerdefinierte IComparer<T>Unterstützung, die Möglichkeit, eine anfängliche Kapazität anzugeben, und aDebuggerTypeProxy der Sammlung leichte Arbeit mit in dem Debugger zu machen.

Es gibt auch eine Inline Version des Pakets, die nur eine einzelne CS-Datei in Ihr Projekt installiert (nützlich, wenn Sie vermeiden möchten, dass extern sichtbare Abhängigkeiten verwendet werden).

Weitere Informationen finden Sie auf der Github-Seite .

ChaseMedallion
quelle
1

Eine einfache Max Heap-Implementierung.

https://github.com/bharathkumarms/AlgorithmsMadeEasy/blob/master/AlgorithmsMadeEasy/MaxHeap.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace AlgorithmsMadeEasy
{
    class MaxHeap
    {
        private static int capacity = 10;
        private int size = 0;
        int[] items = new int[capacity];

        private int getLeftChildIndex(int parentIndex) { return 2 * parentIndex + 1; }
        private int getRightChildIndex(int parentIndex) { return 2 * parentIndex + 2; }
        private int getParentIndex(int childIndex) { return (childIndex - 1) / 2; }

        private int getLeftChild(int parentIndex) { return this.items[getLeftChildIndex(parentIndex)]; }
        private int getRightChild(int parentIndex) { return this.items[getRightChildIndex(parentIndex)]; }
        private int getParent(int childIndex) { return this.items[getParentIndex(childIndex)]; }

        private bool hasLeftChild(int parentIndex) { return getLeftChildIndex(parentIndex) < size; }
        private bool hasRightChild(int parentIndex) { return getRightChildIndex(parentIndex) < size; }
        private bool hasParent(int childIndex) { return getLeftChildIndex(childIndex) > 0; }

        private void swap(int indexOne, int indexTwo)
        {
            int temp = this.items[indexOne];
            this.items[indexOne] = this.items[indexTwo];
            this.items[indexTwo] = temp;
        }

        private void hasEnoughCapacity()
        {
            if (this.size == capacity)
            {
                Array.Resize(ref this.items,capacity*2);
                capacity *= 2;
            }
        }

        public void Add(int item)
        {
            this.hasEnoughCapacity();
            this.items[size] = item;
            this.size++;
            heapifyUp();
        }

        public int Remove()
        {
            int item = this.items[0];
            this.items[0] = this.items[size-1];
            this.items[this.size - 1] = 0;
            size--;
            heapifyDown();
            return item;
        }

        private void heapifyUp()
        {
            int index = this.size - 1;
            while (hasParent(index) && this.items[index] > getParent(index))
            {
                swap(index, getParentIndex(index));
                index = getParentIndex(index);
            }
        }

        private void heapifyDown()
        {
            int index = 0;
            while (hasLeftChild(index))
            {
                int bigChildIndex = getLeftChildIndex(index);
                if (hasRightChild(index) && getLeftChild(index) < getRightChild(index))
                {
                    bigChildIndex = getRightChildIndex(index);
                }

                if (this.items[bigChildIndex] < this.items[index])
                {
                    break;
                }
                else
                {
                    swap(bigChildIndex,index);
                    index = bigChildIndex;
                }
            }
        }
    }
}

/*
Calling Code:
    MaxHeap mh = new MaxHeap();
    mh.Add(10);
    mh.Add(5);
    mh.Add(2);
    mh.Add(1);
    mh.Add(50);
    int maxVal  = mh.Remove();
    int newMaxVal = mh.Remove();
*/
Bharathkumar V.
quelle
-3

Die folgende Implementierung einer PriorityQueueVerwendung SortedSetaus der Systembibliothek.

using System;
using System.Collections.Generic;

namespace CDiggins
{
    interface IPriorityQueue<T, K> where K : IComparable<K>
    {
        bool Empty { get; }
        void Enqueue(T x, K key);
        void Dequeue();
        T Top { get; }
    }

    class PriorityQueue<T, K> : IPriorityQueue<T, K> where K : IComparable<K>
    {
        SortedSet<Tuple<T, K>> set;

        class Comparer : IComparer<Tuple<T, K>> {
            public int Compare(Tuple<T, K> x, Tuple<T, K> y) {
                return x.Item2.CompareTo(y.Item2);
            }
        }

        PriorityQueue() { set = new SortedSet<Tuple<T, K>>(new Comparer()); }
        public bool Empty { get { return set.Count == 0;  } }
        public void Enqueue(T x, K key) { set.Add(Tuple.Create(x, key)); }
        public void Dequeue() { set.Remove(set.Max); }
        public T Top { get { return set.Max.Item1; } }
    }
}
cdiggins
quelle
6
SortedSet.Add schlägt fehl (und gibt false zurück), wenn Sie bereits ein Element im Set mit derselben "Priorität" wie das Element haben, das Sie hinzufügen möchten. Also ... wenn A.Compare (B) == 0 und A bereits in der Liste enthalten sind, schlägt Ihre PriorityQueue.Enqueue-Funktion stillschweigend fehl.
Joseph
Möchten Sie erklären, was T xund sind K key? Ich vermute, dies ist ein Trick, um Duplikate zuzulassen T x, und ich muss einen eindeutigen Schlüssel (z. B. UUID) generieren.
Thariq Nugrohotomo