File d'attente prioritaire en .Net [fermée]

Question

Je recherche une implémentation .NET d'une file d'attente prioritaire ou d'une structure de données en tas

  

Les files d'attente prioritaires sont des structures de données offrant plus de flexibilité que le simple tri, car elles permettent à de nouveaux éléments d'entrer dans un système à des intervalles arbitraires. Il est beaucoup plus économique d'insérer un nouveau travail dans une file d'attente prioritaire que de tout trier de nouveau à chaque arrivée.

     

La file d'attente des priorités de base prend en charge trois opérations principales:

     

  
• Insérer (Q, x). Étant donné un élément x avec la clé k, insérez-le dans la file d'attente prioritaire Q.
  
• Minimum de recherche (Q). Renvoyer un pointeur sur l'élément   dont la valeur de clé est inférieure à toute autre clé de la file d'attente prioritaire   Q.
  
• Supprimer le minimum (Q). Supprimer l'élément de la file d'attente prioritaire Q dont la clé est minimale
  

À moins que je ne regarde au mauvais endroit, il n'y en a pas dans le cadre. Est-ce que quelqu'un en connaît un bon ou dois-je rouler le mien?

Answer 1

J'aime utiliser les classes OrderedBag et OrderedSet de PowerCollections comme files d'attente prioritaires.

Answer 2

Vous pourriez aimer IntervalHeap dans la bibliothèque de collections génériques C5 . Pour citer le guide de l'utilisateur

  

Class IntervalHeap<T> implémente l'interface IPriorityQueue<T> en utilisant un segment d'intervalle stocké sous la forme d'un tableau de paires. Le FindMin et   Les opérations FindMax, et le get-accessor de l'indexeur & # 8217; prennent le temps O (1). Le DeleteMin,   DeleteMax, les opérations d'ajout et de mise à jour et l'accesseur set de l'indexeur & # 8217; prennent du temps   O (log n). Contrairement à une file d'attente prioritaire ordinaire, un segment d'intervalle offre à la fois   et des opérations maximales avec la même efficacité.

L'API est assez simple

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

Installation à partir de Nuget https://www.nuget.org/packages/C5 ou de GitHub https://github.com/sestoft/C5/

Answer 3

Voici ma tentative de création d'un segment .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;
    }
}

Quelques tests:

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

Answer 4

En voici un que je viens d’écrire. Peut-être que ce n’est pas aussi optimisé (utilise seulement un dictionnaire trié) mais simple à comprendre. vous pouvez insérer des objets de différents types, donc pas de files d'attente génériques.

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

        }
    }
}

Answer 5

J'ai trouvé l'un de Julian Bucknall sur son blog ici - http://www.boyet.com /Articles/PriorityQueueCSharp3.html

Nous l'avons légèrement modifié pour que les éléments de faible priorité de la file d'attente finissent par "bouillonner" vers le haut avec le temps, de sorte qu'ils ne souffrent pas de la famine.

Answer 6

Comme mentionné dans les Collections Microsoft pour .NET , Microsoft a écrit (et partagé en ligne) 2 classes PriorityQueue internes dans le .NET Framework. Leur code est disponible pour essayer.

EDIT: Comme l'a commenté @ mathusum-mut, il existe un bogue dans l'une des classes PriorityQueue internes de Microsoft (la communauté SO a bien sûr fourni des correctifs): Bug dans la PriorityQueue interne de Microsoft < T > ;?

Answer 7

Vous pouvez trouver utile cette implémentation: http: / /www.codeproject.com/Articles/126751/Priority-queue-in-Csharp-with-help-of-heap-data-st.aspx

il est générique et basé sur la structure de données en tas

Answer 8

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

facile.

Answer 9

Utilisez un traducteur Java to C # sur l’implémentation Java (java.util.PriorityQueue) du framework Java Collections, ou utilisez plus intelligemment l’algorithme et le code principal et connectez-les à votre propre classe C # en vous conformant au API d'infrastructure de collections C # pour les files d'attente, ou au moins Collections.

Answer 10

AlgoKit

J'ai écrit une bibliothèque open source appelée AlgoKit , disponible via NuGet . Il contient:

• Repères numériques implicites (ArrayHeap),
• tas binomiaux ,
• Couplage des tas .

Le code a été testé de manière approfondie. Je vous recommande de l'essayer.

Exemple

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

Pourquoi ces trois tas?

Le choix optimal d'implémentation dépend fortement des entrées & # 8212; comme le montrent Larkin, Sen et Tarjan dans Une étude empirique sur les files d'attente de priorités, qui remonte à l'essentiel , arXiv: 1403.0252v1 [cs.DS] . Ils ont testé des tas implicites de d-ary, des paires d'appariement, des tas de Fibonacci, des tas de binômes, des tas de d-ary explicites, des tas d'appariement de rangs, des tas de tremblement de terre, des tas de violation, des tas faibles détendus de rang et des tas de Fibonacci stricts.

AlgoKit propose trois types de tas qui semblent être les plus efficaces parmi ceux testés.

Astuce sur le choix

Pour un nombre relativement restreint d’éléments, vous seriez probablement intéressé par l’utilisation de tas implicites, en particulier de tas quaternaires (4-aires implicites). En cas de fonctionnement sur de plus grandes tailles de tas, les structures amorties telles que les tas binomiaux et les tas appariés devraient mieux fonctionner.

Answer 11

Voici une autre implémentation de l'équipe NGenerics:

NGenerics PriorityQueue

Answer 12

J'ai eu le même problème récemment et j'ai fini par créer un paquet NuGet pour cela.

Ceci implémente une file d'attente prioritaire standard basée sur le tas. Il présente également toutes les finesses habituelles des collections BCL: ICollection<T> et IReadOnlyCollection<T> implémentation, support personnalisé IComparer<T>, possibilité de spécifier une capacité initiale et un DebuggerTypeProxy facilitant l'utilisation de la collection dans le débogueur. .

Il existe également une version Inline du package qui en installe un seul. Fichier cs dans votre projet (utile si vous voulez éviter de prendre des dépendances visibles de l'extérieur).

Pour plus d'informations, consultez la page github .

Answer 13

Une implémentation simple de tas max.

https://github.com/bharathkumarms/AlgorithmsMadeasy/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();
*/

Answer 14

La mise en oeuvre suivante d'un PriorityQueue utilise SortedSet à partir de la bibliothèque système.

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