Antrian prioritas dalam .Net [ditutup]

216

Saya mencari implementasi .NET dari antrian prioritas atau struktur data tumpukan

Antrian prioritas adalah struktur data yang memberikan lebih banyak fleksibilitas daripada penyortiran sederhana, karena mereka memungkinkan elemen baru untuk memasuki sistem pada interval sewenang-wenang. Jauh lebih hemat biaya untuk memasukkan pekerjaan baru ke dalam antrian prioritas daripada mengurutkan kembali segala sesuatu pada setiap kedatangan tersebut.

Antrian prioritas dasar mendukung tiga operasi utama:

  • Sisipkan (Q, x). Diberikan item x dengan kunci k, masukkan ke dalam antrian prioritas Q.
  • Cari-Minimum (Q). Kembalikan pointer ke item yang nilai kuncinya lebih kecil dari kunci lainnya di antrian prioritas Q.
  • Hapus-Minimum (Q). Hapus item dari antrian prioritas Q yang kuncinya minimum

Kecuali saya mencari di tempat yang salah, tidak ada satu pun di kerangka itu. Adakah yang tahu yang bagus, atau haruskah saya menggulung sendiri?

Doug McClean
sumber
34
FYI Saya telah mengembangkan antrian prioritas # C yang mudah digunakan, sangat dioptimalkan, yang dapat ditemukan di sini . Itu dikembangkan secara khusus untuk aplikasi pathfinding (A *, dll.), Tetapi harus bekerja dengan sempurna untuk aplikasi lain juga. Saya akan memposting ini sebagai jawaban, tetapi pertanyaan baru-baru ini telah ditutup ...
BlueRaja - Danny Pflughoeft
1
ParallelExtensionsExtras memiliki kode
VoteCoffee
Shamelessly memperkenalkan PriorityQueue , sebagai bagian dari upaya untuk port java API bersamaan ke .net untuk Spring.Net. Keduanya tumpukan dan antrian dengan dukungan generik penuh. Biner dapat diunduh di sini .
Kenneth Xu
@ BlueRaja-DannyPflughoeft Bisakah Anda menambahkan itu sebuah jawaban?
mafu
1
Hanya untuk meringkas. Tidak ada struktur tumpukan data di .net, juga di .net core sekarang. Meskipun Array. Gunakan penggunanya untuk jumlah besar. Ada implementasi internal .
Artyom

Jawaban:

44

Saya suka menggunakan OrderedBagdan OrderedSetkelas di PowerCollections sebagai antrian prioritas.

Ben Hoffstein
sumber
60
OrderedBag / OrderedSet melakukan lebih banyak pekerjaan daripada yang diperlukan, mereka menggunakan pohon merah-hitam alih-alih tumpukan.
Dan Berindei
3
@DanBerindei: tidak perlu bekerja jika Anda perlu membuat perhitungan berjalan (hapus item lama), heap hanya mendukung penghapusan min atau maks
Svisstack
69

Anda mungkin menyukai IntervalHeap dari Perpustakaan Koleksi Generik C5 . Mengutip panduan pengguna

Kelas IntervalHeap<T>mengimplementasikan antarmuka IPriorityQueue<T>menggunakan tumpukan interval yang disimpan sebagai array berpasangan. Operasi FindMin dan FindMax, dan aksesor pengindeks, membutuhkan waktu O (1). Operasi DeleteMin, DeleteMax, Tambah dan Perbarui, dan set-accessor pengindeks, membutuhkan waktu O (log n). Berbeda dengan antrian prioritas biasa, heap interval menawarkan operasi minimum dan maksimum dengan efisiensi yang sama.

APInya cukup sederhana

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

Instal dari Nuget https://www.nuget.org/packages/C5 atau GitHub https://github.com/sestoft/C5/

jaras
sumber
3
Ini terlihat sebagai perpustakaan yang sangat solid dan dilengkapi dengan 1.400 unit tes.
ECC-Dan
2
Saya mencoba untuk menggunakannya tetapi memiliki kekurangan yang serius. IntervalHeap tidak memiliki konsep prioritas bawaan dan memaksa Anda untuk mengimplementasikan IComparable atau IComparer menjadikannya koleksi yang diurutkan bukan "Prioritas". Lebih buruk lagi tidak ada cara langsung untuk memperbarui prioritas dari beberapa entri sebelumnya !!!
morteza khosravi
52

Inilah upaya saya di tumpukan 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;
    }
}

Beberapa tes:

[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
sumber
2
Saya akan merekomendasikan membersihkan nilai tumpukan di ExtractDominating, sehingga tidak berpegang pada objek yang direferensikan lebih lama dari yang diperlukan (potensi kebocoran memori). Untuk tipe nilai itu jelas bukan urusan.
Wout
5
Bagus tetapi Anda tidak dapat menghapus item dari itu? Itu operasi penting untuk antrian prioritas.
Tom Larkworthy
Sepertinya objek yang mendasarinya adalah sebuah array. Bukankah ini lebih baik sebagai pohon biner?
Grunion Shaftoe
1
@OhadSchneider sangat sangat keren, saya hanya melihat ke tumpukan min dan mencoba melakukan apa yang Anda lakukan membuatnya menjadi generik dan tumpukan min atau max! kerja bagus
Gilad
1
@Gilad IEqualityComparer<T>tidak akan cukup, karena itu hanya akan memberi tahu Anda apakah dua item sama, sedangkan Anda perlu tahu hubungan di antara mereka (siapa yang lebih kecil / lebih besar). Memang benar bahwa saya bisa menggunakan IComparer<T>...
Ohad Schneider
23

inilah yang baru saja saya tulis, mungkin itu tidak dioptimalkan (hanya menggunakan kamus yang diurutkan) tetapi mudah dimengerti. Anda dapat memasukkan objek dari berbagai jenis, sehingga tidak ada antrian umum.

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
sumber
ini tidak memungkinkan untuk beberapa entri dengan prioritas yang sama?
Letseatlunch
2
itu benar. ketika Anda memanggil metode Enqueue, itu akan menambahkan item ke antrian prioritas itu. (bagian lain dalam metode enqueue.)
kobi7
5
Apa yang Anda maksud dengan "itu bukan antrian prioritas dalam arti ilmu komputer"? Bagaimana dengan hal itu membuat Anda percaya bahwa ini bukan antrian prioritas?
Mark Byers
14
-1 untuk tidak menggunakan obat generik.
cdiggins
2
Salah satu manfaat terbesar Heap / PriorityQueue adalah kompleksitas O (1) ekstraksi min / max, yaitu operasi Peek. Dan di sini melibatkan pengaturan enumerator, for-loop, dll. Mengapa !? Juga, operasi "Enqueue" daripada menjadi O (logN) - fitur kunci lain dari heap, memiliki satu sapuan O (longN) karena "ContainsKey", yang kedua (lagi O (longN)) untuk menambahkan entri Antrian (jika perlu), yang ketiga untuk benar-benar mengambil Antrian (baris penyimpanan [prio]), dan akhirnya linear menambahkan ke antrian itu. Ini benar-benar gila mengingat implementasi algoritma inti.
Jonan Georgiev
10

Saya menemukan satu oleh Julian Bucknall di blognya di sini - http://www.boyet.com/Articles/PriorityQueueCSharp3.html

Kami memodifikasinya sedikit sehingga item prioritas rendah pada antrian pada akhirnya akan 'melambung' ke atas seiring waktu, sehingga mereka tidak akan menderita kelaparan.

Duncan
sumber
9

Seperti disebutkan dalam Microsoft Collections for .NET , Microsoft telah menulis (dan berbagi secara online) 2 kelas PriorityQueue internal dalam .NET Framework. Kode mereka tersedia untuk dicoba.

EDIT: Seperti yang dikomentari @ mathusum-mut, ada bug di salah satu kelas PriorityQueue internal Microsoft (tentu saja, komunitas SO telah menyediakan perbaikan untuknya): Bug di internal PriorityQueue <T>?

bendung
sumber
10
Bug ditemukan di salah satu implementasi di sini: stackoverflow.com/questions/44221454/...
MathuSum Mut
ohh! Saya dapat melihat bahwa semua kelas ini PriorityQueue<T>dalam sumber bersama Microsoft ditandai dengan penentu internalakses. Jadi mereka hanya digunakan oleh fungsi internal kerangka kerja. Mereka tidak tersedia untuk konsumsi umum hanya dengan merujuk windowsbase.dllpada proyek C #. Satu-satunya cara adalah menyalin sumber bersama ke proyek itu sendiri di dalam file kelas.
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;
    }
}

mudah.

Shimou Dong
sumber
13
Kadang-kadang saya melihat hal-hal seperti for (var n2 = n / 2; n > 0 && comparer.Compare(v, heap[n2]) > 0; n = n2, n2 /= 2) heap[n] = heap[n2]; dan bertanya-tanya apakah itu layak satu lapisan
1
@DustinBreakey gaya pribadi :)
Shimou Dong
3
tapi jelas tidak bisa dibaca orang lain. Pertimbangkan menulis kode yang tidak meninggalkan tanda tanya mengambang di atas kepala pengembang.
alzaimar
3

Gunakan penerjemah Java to C # pada implementasi Java (java.util.PriorityQueue) dalam kerangka Java Collections, atau lebih cerdas gunakan algoritme dan kode inti dan hubungkan ke kelas C # buatan Anda sendiri yang menganut kerangka kerja C # Collections API untuk Antrian, atau setidaknya Koleksi.

Astaga
sumber
Ini berfungsi, tetapi sayangnya IKVM tidak mendukung generik Java, sehingga Anda kehilangan keamanan jenis.
Siput mekanik
8
Tidak ada yang namanya "Java generics" saat Anda berurusan dengan bytecode Java yang dikompilasi. IKVM tidak dapat mendukungnya.
Markus
3

AlgoKit

Saya menulis perpustakaan open source bernama AlgoKit , tersedia melalui NuGet . Itu mengandung:

  • Tumpukan d-ary implisit (ArrayHeap),
  • Tumpukan Binomial ,
  • Tumpukan pasangan .

Kode telah diuji secara luas. Saya merekomendasikan Anda untuk mencobanya.

Contoh

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

Mengapa tiga tumpukan itu?

Pilihan implementasi yang optimal sangat bergantung pada input - seperti yang ditunjukkan Larkin, Sen, dan Tarjan dalam studi empiris back-to-basics tentang antrian prioritas , arXiv: 1403.0252v1 [cs.DS] . Mereka menguji tumpukan d-ary implisit, tumpukan pairing, tumpukan Fibonacci, tumpukan binomial, tumpukan d-ary eksplisit, tumpukan peringkat-pasangan, tumpukan gempa, tumpukan pelanggaran, tumpukan lemah santai-peringkat, dan tumpukan Fibonacci ketat.

AlgoKit menampilkan tiga jenis tumpukan yang tampaknya paling efisien di antara yang diuji.

Petunjuk pilihan

Untuk sejumlah kecil elemen, Anda mungkin akan tertarik menggunakan tumpukan implisit, terutama tumpukan kuaterner (implisit 4-ary). Dalam hal beroperasi pada ukuran tumpukan yang lebih besar, struktur yang diamortisasi seperti tumpukan binomial dan tumpukan pasangan harus bekerja lebih baik.

Patryk Gołębiowski
sumber
1

Saya memiliki masalah yang sama baru-baru ini dan akhirnya membuat paket NuGet untuk ini.

Ini mengimplementasikan antrian prioritas berbasis heap standar. Ia juga memiliki semua koleksi BCL yang biasa: ICollection<T>dan IReadOnlyCollection<T>implementasi, IComparer<T>dukungan khusus , kemampuan untuk menentukan kapasitas awal, danDebuggerTypeProxy untuk membuat koleksi lebih mudah untuk digunakan dalam debugger.

Ada juga versi Inline dari paket yang hanya menginstal file .cs tunggal ke proyek Anda (berguna jika Anda ingin menghindari mengambil dependensi yang terlihat secara eksternal).

Informasi lebih lanjut tersedia di halaman github .

ChaseMedallion
sumber
1

Implementasi Max Heap Sederhana.

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
sumber
-3

Implementasi PriorityQueuepenggunaan berikut SortedSetdari perpustakaan Sistem.

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
sumber
6
SortedSet.Add akan gagal (dan mengembalikan false) jika Anda sudah memiliki item dalam set dengan "prioritas" yang sama dengan item yang Anda coba tambahkan. Jadi ... jika A.Compare (B) == 0 dan A sudah ada dalam daftar, fungsi PriorityQueue.Enqueue Anda akan gagal.
Joseph
Pikiran untuk menjelaskan apa yang T xdan K key? Saya menduga ini adalah trik untuk memungkinkan duplikat T x, dan saya perlu membuat kunci unik (misalnya UUID)?
Thariq Nugrohotomo