it-swarm-tr.com

Net'te öncelik sırası

Bir öncelik sırası veya yığın veri yapısının .NET uygulaması için arıyorum

Öncelik kuyrukları, basit sıralamalardan daha fazla esneklik sağlayan veri yapılarıdır, çünkü yeni elemanların isteğe bağlı aralıklarla bir sisteme girmesine izin verirler. Her yeni varışta her şeyi yeniden sıralamak yerine, öncelik sırasına yeni bir iş eklemek çok daha uygun maliyetlidir.

Temel öncelik sırası, üç birincil işlemi destekler:

  • Ekleme (S, x). K anahtarlı bir x öğesi göz önüne alındığında, Q sırasına öncelik verin.
  • (S)-Minimum Bul. Q önceliği sırasındaki anahtar değeri diğer herhangi bir anahtardan küçük olan öğeye bir işaretçi getirin.
  • (S)-Minimum silin. Maddeyi, anahtarı minimum olan öncelik sırasından Q kaldırın.

Yanlış yere bakmadığım sürece, çerçevede bir tane yok. İyi olanın farkında olan var mı, yoksa kendim mi yapmalıyım?

209
Doug McClean

Öncelik sıraları olarak OrderedBag ve OrderedSet sınıflarını PowerCollections içinde kullanmayı seviyorum.

40
Ben Hoffstein

IntervalHeap'i C5 Genel Koleksiyon Kütüphanesi'nden beğenebilirsiniz. kullanıcı kılavuzunu alıntı yapmak için

IntervalHeap<T> sınıfı, bir çift dizisi olarak depolanan bir aralık öbek kullanarak IPriorityQueue<T> arabirimini uygular. FindMin ve FindMax işlemleri ve indeksleyicinin alma erişimcisi O (1) süresini alır. DeleteMin, DeleteMax, Ekleme ve Güncelleme işlemleri ve indeksleyicinin ayarlayıcısı olarak zaman alır (log n). Sıradan bir öncelik sırasının aksine, bir aralık yığını aynı verimlilikte hem minimum hem de maksimum işlemler sunar.

API yeterince basittir

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

Nuget https://www.nuget.org/packages/C5 veya GitHub'dan https: // github'dan yükleyin com/sestoft/C5/

67
jaras

İşte benim .NET yığın denemem

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

Bazı testler:

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

işte bir yazdım, belki de o kadar optimize edilmiş değil (sadece bir sözlük kullanıyor) ama anlaşılması basit. farklı türde nesneler ekleyebilirsiniz, böylece genel sıralar olmaz.

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

        }
    }
}
21
kobi7

Burada blogunda Julian Bucknall tarafından bir tane buldum - http://www.boyet.com/Articles/PriorityQueueCSharp3.html

Hafifçe değiştirdik, böylece sıradaki düşük öncelikli öğeler zaman içinde yukarı doğru 'kabarcıklandı', böylece açlık çekmeyeceklerdi.

9
Duncan

.NET için Microsoft Koleksiyonlar de belirtildiği gibi, Microsoft, .NET Framework dahilinde (= çevrimiçi paylaşan) 2 iç PriorityQueue sınıfı yazmıştır. Kodları denemek için kullanılabilir.

EDIT: @ mathusum-mut'ın yorumladığı gibi, Microsoft'un dahili PriorityQueue sınıflarından birinde bir hata var (SO topluluğu elbette bunun için düzeltmeler sağlamıştır): Microsoft'un dahili PriorityQueue'daki hata <T>?

7
weir

Bu uygulamayı yararlı bulabilirsiniz: http://www.codeproject.com/Articles/126751/Priority-queue-in-Csharp-with-help-of-heap-data-st.aspx

geneldir ve yığın veri yapısına dayanır.

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

kolay.

6
Shimou Dong

Java uygulamasında Java uygulamasında (Java.util.PriorityQueue) bir Java - C # tercümanı kullanın veya algoritmayı ve çekirdek kodu daha akıllıca kullanın ve bunu, kendi sıraladığınız C # sınıflarına veya en azından Koleksiyonlar için C # Collections çerçeve API'sine bağlı olan bir C # sınıfına takın.

3
JeeBee

AlgoKit

AlgoKit adlı, NuGet adresinde bulunan açık kaynak bir kütüphane yazdım. Bu içerir:

  • Kapalı d-ary yığınları (ArrayHeap),
  • Binom yığınları ,
  • Yığınları eşleştirme .

Kod kapsamlı olarak test edilmiştir. Kesinlikle denemenizi tavsiye ederim.

Örnek

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

Neden bu üç yığın?

En uygun uygulama seçimi, girdilere güçlü bir şekilde bağlıdır - Larkin, Sen ve Tarjan, 'de gösterdiği gibi, öncelik sıralarının , arXiv: 1403.0252v1 [cs.DS] . Örtük yığın yığınlarını, eşleştirme yığınlarını, Fibonacci yığınlarını, binom yığınlarını, açık yığın yığınlarını, rütbe eşleştirme yığınlarını, deprem yığınlarını, ihlal yığınlarını, zayıf gevşeyen zayıf yığınları ve katı Fibonacci yığınlarını test ettiler.

AlgoKit, test edilenler arasında en verimli görünen üç tip yığın sunuyor.

Seçimdeki ipucu

Nispeten az sayıda element için, muhtemelen büyük yığınlar, özellikle dörtlü yığınlar (örtük 4-ary) kullanmak ilginizi çeker. Daha büyük yığın boyutlarında çalıştırma durumunda, binom yığınları ve eşleştirme yığınları gibi amortize edilmiş yapılar daha iyi performans göstermelidir.

3

NGenerics ekibinden bir başka uygulama daha:

NGenerics PriorityQueue

2
husayt

Basit Bir Max Öbek Uygulaması.

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

Son zamanlarda aynı sorunu yaşadım ve bunun için bir NuGet paketi oluşturdum.

Bu, standart bir yığın tabanlı öncelik sırası uygular. Ayrıca, BCL koleksiyonlarının tüm olağan değerlerine sahiptir: ICollection<T> ve IReadOnlyCollection<T> uygulaması, özel IComparer<T> desteği, başlangıç ​​kapasitesini belirleme yeteneği ve bunu yapmak için bir DebuggerTypeProxy toplama hata ayıklayıcı ile çalışmak daha kolay.

Projenize yalnızca tek bir .cs dosyası yükleyen paketin bir Satır içi sürümü de var (dışardan görülebilir bağımlılıklar almaktan kaçınmak istiyorsanız faydalıdır).

github sayfasında hakkında daha fazla bilgi mevcuttur.

1
ChaseMedallion