قائمة الانتظار ذات الأولوية في .Net [مغلق]

StackOverflow https://stackoverflow.com/questions/102398

سؤال

أنا أبحث عن تطبيق .NET لقائمة انتظار الأولوية أو بنية بيانات الكومة

قوائم الانتظار ذات الأولوية هي هياكل بيانات توفر مرونة أكبر من الفرز البسيط، لأنها تسمح لعناصر جديدة بالدخول إلى النظام على فترات زمنية عشوائية.يعد إدراج وظيفة جديدة في قائمة انتظار الأولوية أكثر فعالية من حيث التكلفة بدلاً من إعادة فرز كل شيء عند كل وصول.

تدعم قائمة انتظار الأولوية الأساسية ثلاث عمليات أساسية:

  • إدراج (س، س).بالنظر إلى العنصر x مع المفتاح k، قم بإدراجه في قائمة انتظار الأولوية Q.
  • البحث عن الحد الأدنى (س).إرجاع مؤشر إلى العنصر الذي تكون قيمته الرئيسية أصغر من أي مفتاح آخر في قائمة انتظار الأولوية س.
  • حذف-الحد الأدنى(س).قم بإزالة العنصر من قائمة انتظار الأولوية Q التي يكون مفتاحها هو الحد الأدنى

إلا إذا كنت أبحث في المكان الخطأ، فلا يوجد واحد في الإطار.هل هناك من يعرف فكرة جيدة، أم يجب أن أطرحها بنفسي؟

هل كانت مفيدة؟

المحلول

أنا أحب استخدام OrderedBag و OrderedSet دروس في مجموعات الطاقة كقوائم الانتظار ذات الأولوية.

نصائح أخرى

قد يعجبك IntervalHeap من مكتبة المجموعة العامة C5.على حد تعبير دليل المستخدم

فصل IntervalHeap<T> تنفذ واجهة IPriorityQueue<T> باستخدام كومة الفاصل الزمني المخزنة كمصفوفة من الأزواج.عمليات FindMin و FindMax ، ومستحضر فهرس ، خذ وقتًا O (1).DELETEMIN و DELETEMAX وإضافة وتحديث العمليات ، ومجموعة SET-ACCESSER ، خذ وقتًا O (log n).على عكس قائمة انتظار الأولوية العادية ، يوفر كومة الفاصل الزمني العمليات الدنيا والحد الأقصى بنفس الكفاءة.

واجهة برمجة التطبيقات بسيطة بما فيه الكفاية

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

التثبيت من Nuget https://www.nuget.org/packages/C5 أو جيثب https://github.com/sestoft/C5/

هذه هي محاولتي في كومة .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;
    }
}

بعض الاختبارات:

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

إليك واحدة كتبتها للتو، ربما ليست محسنة (تستخدم فقط قاموسًا مصنفًا) ولكنها سهلة الفهم.يمكنك إدراج كائنات من أنواع مختلفة، لذلك لا توجد قوائم انتظار عامة.

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

        }
    }
}

لقد وجدت واحدًا لجوليان باكنال في مدونته هنا - http://www.boyet.com/Articles/PriorityQueueCSharp3.html

لقد قمنا بتعديلها بشكل طفيف بحيث "ترتفع" العناصر ذات الأولوية المنخفضة في قائمة الانتظار في النهاية إلى الأعلى بمرور الوقت، حتى لا تعاني من المجاعة.

كما ذكر في مجموعات Microsoft لـ .NET, لقد كتبت Microsoft (وشاركتها عبر الإنترنت) 2 فئات PriorityQueue الداخلية ضمن إطار عمل .NET.الكود الخاص بهم متاح للتجربة.

يحرر:كما علق @mathusum-mut، هناك خطأ في إحدى فئات PriorityQueue الداخلية لـ Microsoft (قدم مجتمع SO، بالطبع، إصلاحات له): خطأ في PriorityQueue الداخلي لـ Microsoft<T>؟

قد تجد هذا التنفيذ مفيدًا:http://www.codeproject.com/Articles/126751/Priority-queue-in-Csharp-with-help-of-heap-data-st.aspx

إنه عام ويعتمد على بنية بيانات الكومة

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

سهل.

استخدم مترجم Java إلى C# في تنفيذ Java (java.util.PriorityQueue) في إطار عمل مجموعات Java، أو استخدم الخوارزمية والتعليمات البرمجية الأساسية بشكل أكثر ذكاءً وقم بتوصيلها بفئة C# من صنعك والتي تلتزم بإطار عمل مجموعات C# API لقوائم الانتظار، أو على الأقل المجموعات.

ألغوكيت

لقد كتبت مكتبة مفتوحة المصدر تسمى ألغوكيت, ، متاح عبر نوجيت.أنه يحتوي على:

  • أكوام d-ary الضمنية (صفيف هيب)،
  • أكوام ذات الحدين,
  • أكوام الاقتران.

تم اختبار الكود على نطاق واسع.بالتأكيد أنصحك بتجربتها.

مثال

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

لماذا تلك الأكوام الثلاثة؟

يعتمد الاختيار الأمثل للتنفيذ بشكل كبير على المدخلات - كما يوضح لاركن وسين وتارجان دراسة تجريبية للعودة إلى الأساسيات لقوائم الانتظار ذات الأولوية, أرخايف:1403.0252v1 [cs.DS].لقد اختبروا أكوام d-ary الضمنية، وأكوام الاقتران، وأكوام فيبوناتشي، وأكوام ذات الحدين، وأكوام d-ary الصريحة، وأكوام الاقتران بالرتبة، وأكوام الزلزال، وأكوام الانتهاك، والأكوام الضعيفة المريحة، وأكوام فيبوناتشي الصارمة.

يتميز AlgoKit بثلاثة أنواع من الأكوام التي يبدو أنها الأكثر كفاءة بين تلك التي تم اختبارها.

تلميح حول الاختيار

بالنسبة لعدد صغير نسبيًا من العناصر، من المحتمل أن تكون مهتمًا باستخدام الأكوام الضمنية، وخاصة الأكوام الرباعية (ضمنية 4-ary).في حالة العمل على أحجام كومة أكبر، يجب أن يكون أداء الهياكل المطفأة مثل الأكوام ذات الحدين وأكوام الاقتران أفضل.

إليك تطبيق آخر من فريق NGenerics:

Ngenerics PriorityQueue

واجهت نفس المشكلة مؤخرًا وانتهى بي الأمر بإنشاء ملف حزمة نوجيت لهذا.

يؤدي هذا إلى تنفيذ قائمة انتظار قياسية تعتمد على الكومة.كما أنها تحتوي على جميع التفاصيل المعتادة لمجموعات BCL: ICollection<T> و IReadOnlyCollection<T> التنفيذ، العرف IComparer<T> الدعم والقدرة على تحديد القدرة الأولية، و DebuggerTypeProxy لتسهيل العمل على المجموعة في مصحح الأخطاء.

هناك أيضا في النسق إصدار الحزمة الذي يقوم فقط بتثبيت ملف .cs واحد في مشروعك (مفيد إذا كنت تريد تجنب استخدام تبعيات مرئية خارجيًا).

مزيد من المعلومات متاحة على صفحة جيثب.

تنفيذ بسيط لـ 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();
*/

التنفيذ التالي ل PriorityQueue الاستخدامات SortedSet من مكتبة النظام 

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; } }
    }
}
مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى StackOverflow
scroll top