Prioritätswarteschlange in NET [geschlossen]

Question

Ich bin für eine .NET-Implementierung einer Prioritätswarteschlange oder Heap-Datenstruktur

  

Prioritäts-Warteschlangen sind Datenstrukturen, die mehr Flexibilität als einfaches Sortieren bieten, weil sie neue Elemente erlauben ein System in beliebigen Intervallen einzugeben. Es ist viel kostengünstiger, einen neuen Job in eine Prioritätswarteschlange einzufügen als alles auf jede solchen Ankunft wieder sortiert werden.

     

Die Basisprioritätswarteschlange unterstützt drei Hauptoperationen:

     

  
• Einfügen (Q, x). Bei einem gegebenen Punkt x mit Schlüssel k, legen Sie sie in die Prioritätswarteschlange Q.
  
• Find-Minimum (Q). Gibt einen Zeiger auf das Element   dessen Schlüsselwert kleiner ist als jeder andere Schlüssel in der Prioritäts-Warteschlange   Q.
  
• Löschen-Minimum (Q). Entfernen Sie das Element aus der Prioritätswarteschlange Q, dessen Schlüssel Minimum
  

Wenn ich nicht an der falschen Stelle suchen, gibt es nicht einen im Rahmen. Ist jemand bewusst ein gutes, oder sollte ich meine eigene Rolle?

Answer 1

Ich mag mit den OrderedBag und OrderedSet Klassen in PowerCollections als Prioritäts-Warteschlangen.

Answer 2

Sie vielleicht gefallen IntervalHeap vom C5 Allgemein Sammlung Bibliothek . Um es mit dem Bedienungsanleitung

  

Klasse implementiert IntervalHeap<T> Schnittstelle IPriorityQueue<T> ein Intervall Haufen als ein Array von Paaren gespeichert ist. Die FindMin und   FindMax Operationen und die get-Accessor Indexer, nehmen Sie sich Zeit O (1). Die deletemin,   DeleteMax, Hinzufügen und Aktualisieren von Operationen und der Set-Accessor Indexer, Zeit in Anspruch nehmen   O (log n). Im Gegensatz zu einem gewöhnlichen Prioritätswarteschlange, bietet ein Intervall heap sowohl minimale   und maximale Operationen mit der gleichen Effizienz.

Die API ist einfach genug,

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

Installieren von Nuget https://www.nuget.org/packages/C5 oder GitHub https://github.com/sestoft/C5/

Answer 3

Hier ist mein Versuch eines .NET Haufen

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

Einige 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

Hier ist ein ich gerade schrieb, vielleicht ist es nicht so optimiert (verwendet nur ein sortiertes Wörterbuch), aber einfach zu verstehen. Sie können Objekte verschiedener Arten einsetzen, so dass keine allgemeinen Warteschlangen.

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

Ich fand eine von Julian Bucknall auf seinem Blog hier - http://www.boyet.com /Articles/PriorityQueueCSharp3.html

Ich modifizierte es leicht, so dass Elemente mit niedriger Priorität in der Warteschlange würden ‚Bubble-up‘ schließlich an die Spitze im Laufe der Zeit, so dass sie nicht Hunger leiden.

Answer 6

Wie in Microsoft Kollektionen von .NET erwähnt, hat Microsoft geschrieben (und gemeinsame Online) 2 interne Klassen Priorityqueue innerhalb des .NET Framework. Ihr Code zur Verfügung zu testen.

EDIT: Wie @ mathusum-mut kommentiert, gibt es einen Fehler in einem der Microsoft-internen Klassen Priorityqueue (die SO-Community hat, natürlich, zur Verfügung gestellt Fixes für sie): Bug in Microsofts interner Priorityqueue ?

Answer 7

Sie können nützlich diese Implementierung finden: http: / /www.codeproject.com/Articles/126751/Priority-queue-in-Csharp-with-help-of-heap-data-st.aspx

es ist generisch und basiert auf Heap-Datenstruktur

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

einfach.

Answer 9

Verwenden Sie eine Java zu C # Übersetzer auf der Java-Implementierung (java.util.PriorityQueue) in dem Java Collections Framework oder intelligenter den Algorithmus und Kern-Code verwenden und sie in eine C # Klasse Ihrer eigenen machen stecken, die den haftet C # Collections Framework-API für Warteschlangen oder zumindest Kollektionen.

Answer 10

AlgoKit

Ich schrieb eine Open-Source-Bibliothek namens AlgoKit , erhältlich über NuGet . Es enthält:

• Implicit d-ary Heaps (ArrayHeap)
• Binomial Heaps ,
• Pairing Haufen .

Der Code ausgiebig getestet wurde. Ich empfehle Ihnen auf jeden Fall probieren Sie es aus.

Beispiel

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

Warum diese drei Haufen?

Die optimale Wahl der Implementierung ist stark Eingangsabhängig - wie Larkin, Sen und Tarjan zeigt in Eine Back-to-basics empirische Studie von Prioritäts-Warteschlangen , arXiv: 1403.0252v1 [cs.DS] . Sie testeten implizite d-ary Haufen, Haufen Paarung, Fibonacci-Heaps, binomische Haufen, explizite d-ary Haufen, Rang Paarung Haufen, Beben Haufen, Verletzung Haufen, rang entspannt schwachen Haufen und strenge Fibonacci-Heaps.

AlgoKit verfügt über drei Arten von Halden, die erschienen unter denen getestet werden am effizientesten ist.

Hinweis auf Wahl

Für eine relativ kleine Anzahl von Elementen, würden Sie wahrscheinlich in mit impliziten Heaps interessiert sein, insbesondere quartäre Halden (impliziter 4-ary). Im Falle der auf größeren Speichergrößen arbeiten, amortisieren Strukturen wie binomische Haufen und Paarung Haufen sollte besser.

Answer 11

Hier ist die weitere Implementierung von NGenerics Team:

NGenerics Priorityqueue

Answer 12

Ich hatte das gleiche Problem vor kurzem und am Ende der Schaffung eines NuGet Paket für diesen.

Dies implementiert eine Standard-Heap-basierte Prioritätswarteschlange. Es hat auch alle üblichen Nettigkeiten der BCL Sammlungen. ICollection<T> und IReadOnlyCollection<T> Implementierung, individuelle IComparer<T> Unterstützung, die Fähigkeit, eine Anfangskapazität zu spezifizieren und eine DebuggerTypeProxy die Sammlung zu erleichtern mit im Debugger arbeiten

Es gibt auch eine Inline Version des Pakets, die nur einen einzigen installiert. cs-Datei in Ihr Projekt (nützlich, wenn Sie von außen sichtbar Abhängigkeiten nehmen vermeiden wollen).

Weitere Informationen finden Sie auf der Github Seite zur Verfügung.

Answer 13

Eine einfache Max Heap Implementierung.

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

Answer 14

Die folgende Implementierung eines PriorityQueue verwendet SortedSet aus der Bibliothek-System.

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