Kolejka priorytetowa w .Net [zamknięta]

216

Szukam implementacji .NET struktury danych kolejki priorytetowej lub sterty

Kolejki priorytetowe to struktury danych, które zapewniają większą elastyczność niż proste sortowanie, ponieważ umożliwiają wprowadzanie nowych elementów do systemu w dowolnych odstępach czasu. Znacznie bardziej opłacalne jest wstawianie nowego zadania do kolejki priorytetowej niż ponowne sortowanie wszystkiego przy każdym takim przybyciu.

Podstawowa kolejka priorytetowa obsługuje trzy podstawowe operacje:

  • Wstaw (Q, x). Biorąc pod uwagę element x z kluczem k, wstaw go do kolejki priorytetowej Q.
  • Znajdź minimum (Q). Zwraca wskaźnik do elementu, którego wartość klucza jest mniejsza niż jakikolwiek inny klucz w kolejce priorytetowej Q.
  • Usuń minimum (Q). Usuń element z kolejki priorytetowej Q, której klucz jest minimalny

Jeśli nie szukam w niewłaściwym miejscu, nie ma takiego w ramach. Czy ktoś zdaje sobie sprawę z dobrego, czy powinienem wyrzucić własny?

Doug McClean
źródło
34
Do Twojej wiadomości opracowałem łatwą w użyciu, wysoce zoptymalizowaną kolejkę priorytetową C #, którą można znaleźć tutaj . Został opracowany specjalnie do zastosowań wyszukiwania ścieżek (A * itp.), Ale powinien działać idealnie również w przypadku każdej innej aplikacji. Chciałbym opublikować to jako odpowiedź, ale pytanie zostało niedawno zamknięte ...
BlueRaja - Danny Pflughoeft,
1
ParallelExtensionsExtras ma ConcurrentPriorityQueue code.msdn.microsoft.com/ParExtSamples
VoteCoffee
Bezwstydnie wprowadzamy PriorityQueue , jako część wysiłku przeniesienia równoległego API Java do .net dla Spring.Net. Jest to zarówno stos, jak i kolejka z pełnym ogólnym wsparciem. Plik binarny można pobrać tutaj .
Kenneth Xu
@ BlueRaja-DannyPflughoeft Czy możesz dodać tę odpowiedź?
mafu
1
Podsumowując. Nie ma obecnie struktury danych sterty w .net, ani w rdzeniu .net. Chociaż Array.Sort użytkownicy to dla dużych liczb. Istnieją wewnętrzne wdrożenia .
Artyom,

Odpowiedzi:

44

Lubię używać klas OrderedBagi OrderedSetw PowerCollections jako kolejek priorytetowych.

Ben Hoffstein
źródło
60
OrdersBag / OrdersSet wykonują więcej pracy niż to konieczne, używają czerwono-czarnego drzewa zamiast sterty.
Dan Berindei,
3
@ DanBerindei: niepotrzebna praca, jeśli potrzebujesz wykonać obliczenia bieżące (usuń stare elementy), sterty obsługują tylko usuwanie min lub maks
Svisstack
69

Może Ci się spodobać IntervalHeap z biblioteki kolekcji ogólnej C5 . Cytując instrukcję obsługi

Klasa IntervalHeap<T>implementuje interfejs IPriorityQueue<T>przy użyciu stosu interwałów przechowywanego jako tablica par. Operacje FindMin i FindMax oraz get-accessora indeksatora zajmują czas O (1). Operacje DeleteMin, DeleteMax, Add and Update oraz zestaw indeksujący indeksatora zajmują czas O (log n). W przeciwieństwie do zwykłej kolejki priorytetowej, sterta interwałów oferuje operacje minimalne i maksymalne z tą samą wydajnością.

Interfejs API jest dość prosty

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

Zainstaluj z Nuget https://www.nuget.org/packages/C5 lub GitHub https://github.com/sestoft/C5/

jaras
źródło
3
Wygląda to na bardzo solidną bibliotekę i zawiera 1400 testów jednostkowych.
ECC-Dan
2
Próbowałem go użyć, ale ma poważne wady. IntervalHeap nie ma wbudowanej koncepcji priorytetu i zmusza Cię do wdrożenia IComparable lub IComparer, co sprawia, że ​​jest to posortowana kolekcja, a nie „Priority”. Co gorsza, nie ma bezpośredniego sposobu na aktualizację priorytetu niektórych poprzednich wpisów !!!
morteza khosravi
52

Oto moja próba sterty .NET

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

Niektóre testy:

[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
źródło
2
Poleciłbym wyczyszczenie wartości sterty w ExtractDominating, aby nie utrzymywała obiektu, do którego istnieje odwołanie, dłużej niż to konieczne (potencjalny wyciek pamięci). W przypadku typów wartości nie ma to oczywiście znaczenia.
Wout
5
Fajnie, ale nie możesz usunąć z niego przedmiotów? To ważna operacja w przypadku kolejek priorytetowych.
Tom Larkworthy,
Wygląda na to, że podstawowym obiektem jest tablica. Czy nie byłoby lepiej jako binarne drzewo?
Grunion Shaftoe
1
@OhadSchneider bardzo bardzo fajnie, właśnie patrzyłem na min heap i próbowałem zrobić to, co zrobiłeś, czyniąc to generycznym i min lub max stosem! świetna robota
Gilad
1
@Gilad IEqualityComparer<T>nie wystarczyłoby, ponieważ powiedziałoby to tylko, czy dwa przedmioty są równe, a ty musisz znać relację między nimi (kto jest mniejszy / większy). To prawda, że ​​mogłem skorzystaćIComparer<T> ...
Ohad Schneider
23

oto jeden, który właśnie napisałem, może nie jest tak zoptymalizowany (używa posortowanego słownika), ale jest prosty do zrozumienia. możesz wstawiać obiekty różnego rodzaju, więc nie ma ogólnych kolejek.

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
źródło
nie pozwala to jednak na wiele wpisów o tym samym priorytecie?
Letseatlunch
2
to robi. po wywołaniu metody Enqueue doda element do kolejki o tym priorytecie. (część in else w metodzie
kolejkowania
5
Co rozumiesz przez „tak naprawdę nie jest to kolejka priorytetowa w znaczeniu informatyki”? Co sprawia, że ​​uważasz, że nie jest to kolejka priorytetowa?
Mark Byers,
14
-1 za nieużywanie ogólnych.
cdiggins
2
Jedną z największych zalet Heap / PriorityQueue jest złożoność O (1) ekstrakcji min / max, tj. Operacja Peek. A tutaj chodzi o konfigurację modułu wyliczającego, pętlę for, itp. Dlaczego !? Ponadto operacja „Kolejkuj” zamiast O (logN) - kolejna kluczowa cecha sterty, ma jedno przesunięcie O (longN) z powodu „ContainsKey”, drugie (ponownie O (longN)), aby dodać pozycję kolejki (w razie potrzeby), trzeci do pobierania kolejki (linia pamięci [prio]), a na koniec liniowe dodawanie do tej kolejki. Jest to naprawdę szalone w świetle implementacji algorytmu podstawowego.
Jonan Georgiev
9

Jak wspomniano w zbiorach Microsoft dla platformy .NET , Microsoft napisał (i udostępnił online) 2 wewnętrzne klasy PriorityQueue w .NET Framework. Ich kod jest dostępny do wypróbowania.

EDYCJA: Jak skomentował @ mathusum-mut, w jednej z wewnętrznych klas PriorityQueue Microsoftu jest błąd (społeczność SO oczywiście go naprawiła): Błąd w wewnętrznej PriorityQueue <T> Microsoftu?

jaz
źródło
10
Znaleziono błąd w jednej z implementacji tutaj: stackoverflow.com/questions/44221454/…
MathuSum Mut
och! Widzę, że wszystkie te klasy PriorityQueue<T>we wspólnym źródle Microsoft są oznaczone internalspecyfikatorem dostępu. Są więc używane tylko przez wewnętrzne funkcjonalności frameworka. Nie są one dostępne do powszechnego użytku po prostu przez odwołanie windowsbase.dllw projekcie C #. Jedynym sposobem jest skopiowanie udostępnionego źródła do samego projektu w pliku klasy.
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;
    }
}

łatwo.

Shimou Dong
źródło
13
Czasami widzę takie rzeczy for (var n2 = n / 2; n > 0 && comparer.Compare(v, heap[n2]) > 0; n = n2, n2 /= 2) heap[n] = heap[n2]; i zastanawiam się, czy warto było mieć jedną podszewkę
1
@DustinBreakey osobisty styl :)
Shimou Dong
3
ale zdecydowanie nieczytelne dla innych. Rozważ napisanie kodu, który nie pozostawia znaku zapytania unoszącego się nad głową programisty.
alzaimar
3

Użyj translatora Java do C # na implementacji Java (java.util.PriorityQueue) w ramach kolekcji Java lub bardziej inteligentnie użyj algorytmu i kodu rdzenia i podłącz go do własnej klasy C #, co jest zgodne z ramą kolekcji C # Interfejs API dla kolejek lub przynajmniej kolekcji.

JeeBee
źródło
To działa, ale niestety IKVM nie obsługuje generycznych Java, więc tracisz bezpieczeństwo typu.
Mechaniczny ślimak
8
W przypadku skompilowanego kodu bajtowego Java nie ma czegoś takiego jak „ogólne Java”. IKVM nie obsługuje tego.
Mark
3

AlgoKit

Napisałem bibliotekę open source o nazwie AlgoKit , dostępną za pośrednictwem NuGet . Zawiera:

  • Domniemane hałdy d-ary (ArrayHeap),
  • Hałdy dwumianowe ,
  • Parowanie hałd .

Kod został gruntownie przetestowany. Zdecydowanie polecam spróbować.

Przykład

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);

Dlaczego te trzy hałdy?

Optymalny wybór implementacji jest silnie zależny od nakładów - jak pokazują Larkin, Sen i Tarjan w A-back-to-podstawy studium empirycznym kolejek priorytetowych , arXiv: 1403.0252v1 [cs.DS] . Testowali niejawne stosy d-ary, stosy parowania, stosy Fibonacciego, stosy dwumianowe, jawne stosy d-ary, stosy parowania rang, stosy trzęsień, stosy naruszenia, stosy osłabione rangą osłabione i surowe stosy Fibonacciego.

AlgoKit zawiera trzy rodzaje hałd, które wydają się najbardziej wydajne wśród testowanych.

Wskazówka dotycząca wyboru

W przypadku stosunkowo niewielkiej liczby elementów prawdopodobnie zainteresowałbyś się stosami niejawnymi, zwłaszcza stertami czwartorzędowymi (niejawne 4-ary). W przypadku operacji na większych rozmiarach, amortyzowane struktury, takie jak stosy dwumianowe i stosy parowania, powinny działać lepiej.

Patryk Gołębiowski
źródło
1

Ostatnio miałem ten sam problem i ostatecznie stworzyłem do tego pakiet NuGet .

To implementuje standardową kolejkę priorytetową opartą na stercie. Ma również wszystkie typowe cechy kolekcji BCL: ICollection<T>i IReadOnlyCollection<T>implementację, niestandardowe IComparer<T>wsparcie, możliwość określenia początkowej pojemności orazDebuggerTypeProxy ułatwienie pracy z kolekcją w debuggerze.

Istnieje również wersja Inline pakietu, która po prostu instaluje jeden plik .cs w twoim projekcie (przydatne, jeśli chcesz uniknąć przyjmowania zewnętrznych widocznych zależności).

Więcej informacji jest dostępnych na stronie github .

ChaseMedallion
źródło
1

Prosta implementacja Max Heap.

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.
źródło
-3

Następująca implementacja PriorityQueuezastosowań SortedSetz biblioteki System.

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
źródło
6
SortedSet.Add zakończy się niepowodzeniem (i zwróci false), jeśli masz już element w zestawie o takim samym „priorytecie” jak element, który próbujesz dodać. Więc ... jeśli A.Compare (B) == 0 i A jest już na liście, twoja funkcja PriorityQueue.Enqueue po cichu zawiedzie.
Joseph
Pilnuj, aby wyjaśnić, jakie są T xi K key? Zgaduję, że jest to sztuczka pozwalająca na duplikowanie T xi muszę wygenerować unikalny klucz (np. UUID)?
Thariq Nugrohotomo