Cola de prioridad en .Net

Estoy buscando una implementación de .NET de una cola de prioridad o estructura de datos de montón

Las colas de prioridad son estructuras de datos que proporcionan más flexibilidad que la clasificación simple, porque permiten que los nuevos elementos ingresen a un sistema a intervalos arbitrarios. Es mucho más rentable insertar un nuevo trabajo en una cola de prioridad que volver a ordenar todo en cada llegada.

La cola de prioridad básica admite tres operaciones principales:

  • Insertar (Q, x). Dado un elemento x con la clave k, insértelo en la cola de prioridad Q.
  • Buscar-Mínimo (Q). Devuelve un puntero al elemento cuyo valor clave es más pequeño que cualquier otra clave en la cola de prioridad Q.
  • Delete-Minimum (Q). Eliminar el elemento de la cola de prioridad Q cuya clave es mínima

A menos que esté buscando en el lugar equivocado, no hay uno en el marco. ¿Alguien está enterado de uno bueno, o debería lanzar el mío?

Me gusta utilizar las clases OrderedBag y OrderedSet en PowerCollections como colas de prioridad.

Es posible que le guste IntervalHeap de la Biblioteca de colecciones genéricas de C5 . Para citar la guía del usuario

La clase IntervalHeap implementa la interfaz IPriorityQueue usando un almacenamiento IPriorityQueue intervalo almacenado como una matriz de pares. Las operaciones FindMin y FindMax, y el get-accessor del indexador, toman tiempo O (1). Las operaciones DeleteMin, DeleteMax, Add and Update y el set-accessor del indexador toman tiempo O (log n). A diferencia de una cola de prioridad normal, un montón de intervalos ofrece operaciones mínimas y máximas con la misma eficacia.

La API es lo suficientemente simple

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

Instalar desde Nuget https://www.nuget.org/packages/C5 o GitHub https://github.com/sestoft/C5/

Aquí está mi bash en un montón de .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; } } 

Algunas pruebas:

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

Aquí hay uno que acabo de escribir, tal vez no esté tan optimizado (solo usa un diccionario ordenado) pero es fácil de entender. puede insertar objetos de diferentes tipos, de modo que no haya colas genéricas.

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

Encontré uno de Julian Bucknall en su blog aquí – http://www.boyet.com/Articles/PriorityQueueCSharp3.html

Lo modificamos ligeramente para que los artículos de baja prioridad en la cola eventualmente ‘saltaran’ a la cima a lo largo del tiempo, para que no sufrieran inanición.

Puede encontrar útil esta implementación: http://www.codeproject.com/Articles/126751/Priority-queue-in-Csharp-with-help-of-heap-data-st.aspx

es genérico y se basa en la estructura de datos del montón

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

fácil.

Como se menciona en Microsoft Collections para .NET , Microsoft ha escrito (y compartido en línea) 2 clases internas PriorityQueue dentro de .NET Framework. Su código está disponible para probar.

EDITAR: Como @matususum-mut comentó, hay un error en una de las clases PriorityQueue internas de Microsoft (la comunidad SO, por supuesto, ha proporcionado correcciones): ¿ Error en PriorityQueue ?

Use un traductor de Java a C # en la implementación de Java (java.util.PriorityQueue) en el marco de Java Collections, o use de manera más inteligente el algoritmo y el código central y conéctelo a una clase C # de su propia creación que se adhiera al marco C # Collections API para colas, o al menos colecciones.

Aquí está la otra implementación del equipo de NGenerics:

NGenerics PriorityQueue

AlgoKit

Escribí una biblioteca de código abierto llamada AlgoKit , disponible a través de NuGet . Contiene:

  • Montones d-ary implícitos (ArrayHeap),
  • Montones binomiales ,
  • Emparejar montones .

El código ha sido ampliamente probado. Definitivamente te recomiendo que lo pruebes.

Ejemplo

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

¿Por qué esos tres montones?

La elección óptima de la implementación depende en gran medida de la entrada, como demuestran Larkin, Sen y Tarjan en un estudio empírico de las colas de prioridad , arXiv: 1403.0252v1 [cs.DS] . Probaron montones d-ary implícitos, montones de apareamiento, montones de Fibonacci, montones binomiales, montones de arcos explícitos, montones de apareamiento de rango, montones de temblores, montones de infracciones, montículos débiles de rango relajado y montones de Fibonacci estrictos.

AlgoKit presenta tres tipos de montones que parecían ser los más eficientes entre los probados.

Sugerencia sobre la elección

Para un número relativamente pequeño de elementos, es probable que esté interesado en utilizar montones implícitos, especialmente montones cuaternarios (4-ary implícitos). En el caso de operar en tamaños de montón más grandes, las estructuras amortizadas como montones binomiales y montones de emparejamiento deberían tener un mejor rendimiento.

Tuve el mismo problema recientemente y terminé creando un paquete NuGet para esto.

Esto implementa una cola de prioridad basada en el montón estándar. También tiene todas las sutilezas habituales de las colecciones BCL: implementación ICollection e IReadOnlyCollection , IComparer personalizado IComparer , capacidad para especificar una capacidad inicial, y un DebuggerTypeProxy para hacer que la colección sea más fácil de trabajar en el depurador

También hay una versión en línea del paquete que simplemente instala un único archivo .cs en su proyecto (útil si desea evitar tener dependencias visibles externamente).

Hay más información disponible en la página de github .

Una implementación Simple 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(); */ 

La siguiente implementación de PriorityQueue usa SortedSet de la biblioteca del 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; } } } }