Coda prioritaria in .Net

Sto cercando un’implementazione .NET di una coda di priorità o di una struttura di dati dell’heap

Le code prioritarie sono strutture di dati che offrono maggiore flessibilità rispetto all’ordinamento semplice, poiché consentono a nuovi elementi di entrare in un sistema a intervalli arbitrari. È molto più conveniente inserire un nuovo lavoro in una coda di priorità piuttosto che riordinare tutto su ogni arrivo.

La coda di priorità di base supporta tre operazioni principali:

  • Inserisci (Q, x). Dato un elemento x con la chiave k, inserirlo nella coda di priorità Q.
  • Trova-minima (Q). Restituisce un puntatore all’elemento il cui valore chiave è inferiore a qualsiasi altra chiave nella coda di priorità Q.
  • Elimina-minima (Q). Rimuovi l’articolo dalla coda di priorità Q la cui chiave è minima

A meno che non stia cercando nel posto sbagliato, non ce n’è uno nel framework. Qualcuno è a conoscenza di uno buono o dovrei lanciare il mio?

    Mi piace usare le classi OrderedBag e OrderedSet in PowerCollections come code prioritarie.

    Potresti gradire IntervalHeap dalla libreria C5 Generic Collection . Per citare la guida dell’utente

    Class IntervalHeap implementa l’interfaccia IPriorityQueue utilizzando un heap di intervalli memorizzato come una matrice di coppie. Le operazioni FindMin e FindMax e l’accessorizzatore dell’indicizzatore richiedono tempo O (1). Le operazioni DeleteMin, DeleteMax, Add e Update e l’accessor set-set dell’indicizzatore richiedono tempo O (log n). A differenza di una normale coda di priorità, un heap di intervalli offre operazioni sia minima che massima con la stessa efficienza.

    L’API è abbastanza semplice

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

    Installa da Nuget https://www.nuget.org/packages/C5 o GitHub https://github.com/sestoft/C5/

    Ecco il mio tentativo in un heap .NET

     public abstract class Heap : IEnumerable { 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 Comparer { get; private set; } protected abstract bool Dominates(T x, T y); protected Heap() : this(Comparer.Default) { } protected Heap(Comparer comparer) : this(Enumerable.Empty(), comparer) { } protected Heap(IEnumerable collection) : this(collection, Comparer.Default) { } protected Heap(IEnumerable collection, Comparer 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 GetEnumerator() { return _heap.Take(Count).GetEnumerator(); } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } } public class MaxHeap : Heap { public MaxHeap() : this(Comparer.Default) { } public MaxHeap(Comparer comparer) : base(comparer) { } public MaxHeap(IEnumerable collection, Comparer comparer) : base(collection, comparer) { } public MaxHeap(IEnumerable collection) : base(collection) { } protected override bool Dominates(T x, T y) { return Comparer.Compare(x, y) >= 0; } } public class MinHeap : Heap { public MinHeap() : this(Comparer.Default) { } public MinHeap(Comparer comparer) : base(comparer) { } public MinHeap(IEnumerable collection) : base(collection) { } public MinHeap(IEnumerable collection, Comparer comparer) : base(collection, comparer) { } protected override bool Dominates(T x, T y) { return Comparer.Compare(x, y) <= 0; } } 

    Alcuni test:

     [TestClass] public class HeapTests { [TestMethod] public void TestHeapBySorting() { var minHeap = new MinHeap(new[] {9, 8, 4, 1, 6, 2, 7, 4, 1, 2}); AssertHeapSort(minHeap, minHeap.OrderBy(i => i).ToArray()); minHeap = new MinHeap { 7, 5, 1, 6, 3, 2, 4, 1, 2, 1, 3, 4, 7 }; AssertHeapSort(minHeap, minHeap.OrderBy(i => i).ToArray()); var maxHeap = new MaxHeap(new[] {1, 5, 3, 2, 7, 56, 3, 1, 23, 5, 2, 1}); AssertHeapSort(maxHeap, maxHeap.OrderBy(d => -d).ToArray()); maxHeap = new MaxHeap {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 heap, IEnumerable expected) { var sorted = new List(); while (heap.Count > 0) sorted.Add(heap.ExtractDominating()); Assert.IsTrue(sorted.SequenceEqual(expected)); } } 

    ecco uno che ho appena scritto, forse non è così ottimizzato (usa solo un dizionario ordinato) ma semplice da capire. puoi inserire oggetti di diverso tipo, quindi nessuna coda generica.

     using System; using System.Diagnostics; using System.Collections; using System.Collections.Generic; namespace PrioQueue { public class PrioQueue { int total_size; SortedDictionary storage; public PrioQueue () { this.storage = new SortedDictionary (); 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++; } } } 

    Ne ho trovato uno da Julian Bucknall sul suo blog qui – http://www.boyet.com/Articles/PriorityQueueCSharp3.html

    Lo abbiamo modificato leggermente in modo che gli elementi a bassa priorità nella coda finissero “a gonfiarsi” verso l’alto nel tempo, quindi non avrebbero sofferto di fame.

    Potresti trovare utile questa implementazione: http://www.codeproject.com/Articles/126751/Priority-queue-in-Csharp-with-help-of-heap-data-st.aspx

    è generico e basato sulla struttura dei dati dell’heap

     class PriorityQueue { IComparer comparer; T[] heap; public int Count { get; private set; } public PriorityQueue() : this(null) { } public PriorityQueue(int capacity) : this(capacity, null) { } public PriorityQueue(IComparer comparer) : this(16, comparer) { } public PriorityQueue(int capacity, IComparer comparer) { this.comparer = (comparer == null) ? Comparer.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; } } 

    facile.

    Come accennato in Microsoft Collections per .NET , Microsoft ha scritto (e condiviso online) 2 classi interne di PriorityQueue all’interno di .NET Framework. Il loro codice è disponibile per provare.

    EDIT: Come @ mathusum-mut ha commentato, c’è un bug in una delle classi interne di PriorityQueue di Microsoft (la comunità SO ha, ovviamente, fornito delle correzioni per questo): Bug in Microsoft PriorityQueue interno ?

    Utilizzare un convertitore da Java a C # sull’implementazione Java (java.util.PriorityQueue) nel framework Collezioni Java o utilizzare in modo più intelligente l’algoritmo e il codice di base e collegarlo a una class C # che faccia aderire al framework C # Collections API per code o almeno raccolte.

    Ecco un’altra implementazione dal team di NGenerics:

    NGenerics PriorityQueue

    AlgoKit

    Ho scritto una libreria open source chiamata AlgoKit , disponibile tramite NuGet . Contiene:

    • Cumuli d-ary impliciti (ArrayHeap),
    • Cumuli binomiali ,
    • Accoppiamento degli heap .

    Il codice è stato ampiamente testato. Consiglio vivamente di provarlo.

    Esempio

     var comparer = Comparer.Default; var heap = new PairingHeap(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); 

    Perché quei tre cumuli?

    La scelta ottimale di implementazione è fortemente dipendente dall’input – come Larkin, Sen e Tarjan mostrano in uno studio empirico di back-to-basics sulle code di priorità , arXiv: 1403.0252v1 [cs.DS] . Esaminarono ammassi di d-ary impliciti, ammassi di accoppiamenti, cumuli di Fibonacci, cumuli binomiali, cumuli di d-ary espliciti, cumuli di accoppiamento di gradi, cumuli di terremoto, cumuli di violazioni, cumuli deboli rilassati di rango e rigidi cumuli di Fibonacci.

    AlgoKit presenta tre tipi di heap che sembravano essere i più efficienti tra quelli testati.

    Suggerimento sulla scelta

    Per un numero relativamente piccolo di elementi, è probabile che siate interessati all’uso di heap impliciti, in particolare heap quaternari (implicito 4-ary). In caso di funzionamento su dimensioni di heap più grandi, le strutture ammortizzate come gli heap binomiali e gli heap di accoppiamento dovrebbero avere prestazioni migliori.

    Ho avuto lo stesso problema di recente e ho finito per creare un pacchetto NuGet per questo.

    Questo implementa una coda di priorità basata su heap standard. Ha anche tutte le usuali sottigliezze delle raccolte BCL: ICollection e IReadOnlyCollection implementazione, supporto personalizzato di IComparer , capacità di specificare una capacità iniziale e un DebuggerTypeProxy per rendere la raccolta più facile da lavorare nel debugger.

    C’è anche una versione Inline del pacchetto che installa un singolo file .cs nel tuo progetto (utile se vuoi evitare di prendere dipendenze esternamente visibili).

    Ulteriori informazioni sono disponibili sulla pagina github .

    Una implementazione di Max Heap semplice.

    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(); */ 

    La seguente implementazione di PriorityQueue utilizza SortedSet dalla libreria di sistema.

     using System; using System.Collections.Generic; namespace CDiggins { interface IPriorityQueue where K : IComparable { bool Empty { get; } void Enqueue(T x, K key); void Dequeue(); T Top { get; } } class PriorityQueue : IPriorityQueue where K : IComparable { SortedSet> set; class Comparer : IComparer> { public int Compare(Tuple x, Tuple y) { return x.Item2.CompareTo(y.Item2); } } PriorityQueue() { set = new SortedSet>(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; } } } }