Cola prioritaria en .Net [cerrado]

216

Estoy buscando una implementación .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 simple clasificación, ya que permiten que nuevos elementos ingresen a un sistema a intervalos arbitrarios. Es mucho más rentable insertar un nuevo trabajo en una cola prioritaria 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). Devuelva un puntero al elemento cuyo valor de clave es menor que cualquier otra clave en la cola de prioridad Q.
  • Eliminar-Mínimo (Q). Elimine el elemento de la cola de prioridad Q cuya clave es mínima

A menos que esté buscando en el lugar equivocado, no hay ninguno en el marco. ¿Alguien sabe de uno bueno, o debo rodar el mío?

Doug McClean
fuente
34
Para su información, he desarrollado una cola de prioridad C # fácil de usar y altamente optimizada, que se puede encontrar aquí . Fue desarrollado específicamente para aplicaciones de búsqueda de rutas (A *, etc.), pero también debería funcionar perfectamente para cualquier otra aplicación. Publicaría esto como respuesta, pero la pregunta se ha cerrado recientemente ...
BlueRaja - Danny Pflughoeft
1
ParallelExtensionsExtras tiene un ConcurrentPriorityQueue code.msdn.microsoft.com/ParExtSamples
VoteCoffee
Introducir descaradamente PriorityQueue , como parte del esfuerzo para portar API concurrente de Java a .net para Spring.Net. Es tanto un montón como una cola con soporte genérico completo. Binario se puede descargar aquí .
Kenneth Xu
@ BlueRaja-DannyPflughoeft ¿Podría agregar una respuesta?
mafu
1
Solo para resumir. No hay estructura de datos de montón en .net, ni en .net core ahora. Aunque Array.Sort lo usa para grandes cantidades. Existen implementaciones internas .
Artyom

Respuestas:

44

Me gusta usar las clases OrderedBagy OrderedSeten PowerCollections como colas de prioridad.

Ben Hoffstein
fuente
6060
OrderedBag / OrderedSet hacen más trabajo del necesario, usan un árbol rojo-negro en lugar de un montón.
Dan Berindei el
3
@DanBerindei: no es necesario trabajar si necesita hacer un cálculo en ejecución (eliminar elementos antiguos), el montón solo admite la eliminación de mínimo o máximo
Svisstack
69

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

La clase IntervalHeap<T>implementa la interfaz IPriorityQueue<T>usando un montón de intervalos almacenado como una matriz de pares. Las operaciones FindMin y FindMax, y el get-accessor del indexador, toman el 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 ordinaria, un montón de intervalos ofrece operaciones mínimas y máximas con la misma eficiencia.

La API es lo suficientemente simple

> var heap = new C5.IntervalHeap<int>();
> 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/

jaras
fuente
3
Esto parece ser una biblioteca muy sólida y viene con 1400 pruebas unitarias.
ECC-Dan
2
Traté de usarlo pero tiene serias fallas. IntervalHeap no tiene un concepto integrado de prioridad y lo obliga a implementar IComparable o IComparer, lo que lo convierte en una colección ordenada, no en una "Prioridad". ¡Peor aún, no hay forma directa de actualizar la prioridad de alguna entrada anterior!
morteza khosravi
52

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

Algunas pruebas:

[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
fuente
2
Recomendaría borrar el valor de almacenamiento dinámico en ExtractDominating, para que no se aferre al objeto referenciado más de lo necesario (pérdida potencial de memoria). Para los tipos de valor, obviamente no es una preocupación.
Wout
55
¿Agradable pero no puedes eliminar elementos de él? Esa es una operación importante para las colas prioritarias.
Tom Larkworthy
Parece que el objeto subyacente es una matriz. ¿No sería esto mejor como árbol binario?
Grunion Shaftoe
1
@OhadSchneider muy, muy genial, ¡solo estaba buscando en el montón mínimo e intenté hacer lo que hiciste para que sea genérico y el montón mínimo o máximo! gran trabajo
Gilad
1
@Gilad IEqualityComparer<T>no sería suficiente, ya que eso solo le diría si dos elementos son iguales, mientras que necesita saber la relación entre ellos (quién es más pequeño / más grande). Sin IComparer<T>embargo, es cierto que podría haber usado ...
Ohad Schneider
23

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, por lo que no hay colas genéricas.

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
fuente
sin embargo, esto no permite múltiples entradas con la misma prioridad?
Letseatlunch
2
lo hace. cuando invoque el método Enqueue, agregará el elemento a la cola de esa prioridad. (la parte en else en el método en cola.)
kobi7
55
¿Qué quiere decir con "no es realmente una cola prioritaria en el significado de la informática"? ¿Qué te hace creer que esto no es una cola prioritaria?
Mark Byers
14
-1 por no usar genéricos.
cdiggins
2
Uno de los mayores beneficios de Heap / PriorityQueue es la complejidad O (1) de la extracción min / max, es decir, la operación Peek. Y aquí involucra la configuración del enumerador, for-loop, etc. ¿Por qué? Además, la operación "Enqueue" en lugar de ser O (logN), otra característica clave del montón, tiene un deslizamiento O (longN) debido a "ContainsKey", un segundo (nuevamente O (longN)) para agregar la entrada de la cola (si es necesario), un tercero para recuperar realmente la Cola (la línea de almacenamiento [prio]), y finalmente una adición lineal a esa cola. Esto es realmente una locura a la luz de la implementación del algoritmo central.
Jonan Georgiev el
9

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

EDITAR: Como comentó @ mathusum-mut, hay un error en una de las clases internas de PriorityQueue de Microsoft (la comunidad SO, por supuesto, ha proporcionado soluciones): ¿ Error en el PriorityQueue <T> interno de Microsoft?

presa
fuente
10
Se encontró un error en una de las implementaciones aquí: stackoverflow.com/questions/44221454/…
MathuSum Mut
ohh! Puedo ver que todas estas clases PriorityQueue<T>en la fuente compartida de Microsoft están marcadas con un internalespecificador de acceso. Por lo tanto, solo los utilizan las funcionalidades internas del marco. No están disponibles para el consumo general simplemente al referirse windowsbase.dlla un proyecto de C #. La única forma es copiar la fuente compartida en el proyecto dentro de un archivo de clase.
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;
    }
}

fácil.

Shimou Dong
fuente
13
A veces veo cosas como for (var n2 = n / 2; n > 0 && comparer.Compare(v, heap[n2]) > 0; n = n2, n2 /= 2) heap[n] = heap[n2]; y me pregunto si valió la pena
1
@DustinBreakey estilo personal :)
Shimou Dong
3
pero definitivamente no legible para otros. Considere escribir un código que no deje un signo de interrogación flotando sobre la cabeza del desarrollador.
alzaimar
3

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 de C # propia que se adhiera al marco de C # Collections API para colas, o al menos colecciones.

JeeBee
fuente
Esto funciona, pero desafortunadamente IKVM no admite genéricos de Java, por lo que pierde la seguridad de los tipos.
Caracol mecánico el
8
No existen los "genéricos de Java" cuando se trata de un código de bytes Java compilado. IKVM no puede soportarlo.
Mark
3

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 ,
  • Emparejamiento de montones .

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

Ejemplo

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

¿Por qué esos tres montones?

La elección óptima de implementación depende en gran medida de la entrada, como muestran Larkin, Sen y Tarjan en un estudio empírico de regreso a lo básico de colas prioritarias , arXiv: 1403.0252v1 [cs.DS] . Probaron montones d-ary implícitos, montones de pares, montones de Fibonacci, montones binomiales, montones d-ary explícitos, montones de pares de rango, montones de terremotos, montones de violación, montones débiles relajados y montones estrictos de Fibonacci.

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

Sugerencia sobre la elección

Para un número relativamente pequeño de elementos, es probable que le interese usar montones implícitos, especialmente montones cuaternarios (4 arios implícitos). En caso de operar en tamaños de almacenamiento dinámico más grandes, las estructuras amortizadas como los montones binomiales y los montones de pares deberían funcionar mejor.

Patryk Gołębiowski
fuente
1

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

Esto implementa una cola de prioridad estándar basada en el montón. También tiene todas las sutilezas habituales de las colecciones BCL: ICollection<T>e IReadOnlyCollection<T>implementación, IComparer<T>soporte personalizado , capacidad para especificar una capacidad inicial y unDebuggerTypeProxy 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 tomar dependencias visibles desde el exterior).

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

ChaseMedallion
fuente
1

Una implementación simple de 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
fuente
-3

La siguiente implementación de un PriorityQueueusos SortedSetde la biblioteca del sistema.

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
fuente
66
SortedSet.Add fallará (y devolverá falso) si ya tiene un elemento en el conjunto con la misma "prioridad" que el elemento que está tratando de agregar. Entonces ... si A.Compare (B) == 0 y A ya está en la lista, su función PriorityQueue.Enqueue fallará silenciosamente.
Joseph
¿Te importaría explicar qué son T xy qué K key? Supongo que este es un truco para permitir duplicados T x, y necesito generar una clave única (por ejemplo, UUID).
Thariq Nugrohotomo