의 우선 순위 대기열입니다.그물

의 우선 순위 대기열입니다.그물

마감되었습니다. 이 질문은 책, 도구, 소프트웨어 라이브러리 등에 대한 추천을 구하는 것입니다.충족되지 않습니다.스택 오버플로 지침입니다.현재 답변을 수락하고 있지 않습니다.

---

책, 도구, 소프트웨어 라이브러리 등에 대한 추천을 구하는 질문은 허용되지 않습니다.질문에 사실과 인용문으로 답변할 수 있도록 질문을 편집할 수 있습니다.

6년 전에 문을 닫았습니다.

이 질문을 개선합니다.

우선 순위 큐 또는 힙 데이터 구조의 .NET 구현을 찾고 있습니다.

우선 순위 대기열은 새 요소가 임의의 간격으로 시스템에 들어갈 수 있기 때문에 단순 정렬보다 유연성을 제공하는 데이터 구조입니다.각 도착 시 모든 작업을 다시 정렬하는 것보다 새 작업을 우선 순위 대기열에 삽입하는 것이 훨씬 비용 효율적입니다.

기본 우선 순위 대기열은 세 가지 기본 작업을 지원합니다.

• 삽입(Q,x). 키가 k인 항목 x를 지정하면 우선 순위 대기열 Q에 삽입합니다.
• 찾기-최소(Q).키 값이 우선 순위 대기열 Q의 다른 키보다 작은 항목으로 포인터를 반환합니다.
• 삭제-최소(Q).키가 최소인 우선 순위 대기열 Q에서 항목 제거

제가 잘못된 곳을 찾지 않는 한, 틀에 하나도 없습니다.누구 좋은 거 아는 사람 있어요? 아니면 제가 직접 굴려야 하나요?

C5 일반 컬렉션 라이브러리에서 IntervalHeap을 사용할 수 있습니다.사용자 안내서 인용하기

급IntervalHeap<T> 구현IPriorityQueue<T>쌍 배열로 저장된 간격 힙을 사용합니다. 그FindMin그리고.FindMax작업 및 인덱서의 get-accessor는 O(1) 시간이 걸립니다. 그DeleteMin,DeleteMax추가 및 업데이트 작업과 인덱서의 Set-accessor는 O(로그 n) 시간이 걸립니다.일반적인 우선 순위 대기열과 달리 간격 힙은 동일한 효율성으로 최소 및 최대 작업을 모두 제공합니다.

API는 매우 간단합니다.

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

Nuget https://www.nuget.org/packages/C5 또는 GitHub 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));
    }
}

나는 그것을 사용하는 것을 좋아합니다.OrderedBag그리고.OrderedSet우선 순위 큐로 PowerCollections의 클래스를 지정합니다.

여기 제가 방금 쓴 것이 있습니다, 아마도 그것은 최적화되지 않았을 것입니다(그냥 정렬된 사전을 사용합니다). 하지만 이해하기 쉽습니다.다른 종류의 개체를 삽입할 수 있으므로 일반 대기열이 없습니다.

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

        }
    }
}

.NET 6+: @rustyx가 언급했듯이 .NET 6은 시스템을 추가합니다.컬렉션.일반적인.우선순위대기열<TELENT,TP 우선 순위 > 클래스입니다.그리고 FWIW는 오픈 소스이며 c#로 구현됩니다.

이전 버전의 .NET Core 및 .NET Framework: Microsoft는 2개의 내부 우선 순위를 작성(및 온라인 공유)했습니다..NET Framework 내에서 클래스를 큐에 넣습니다.그러나 @mathusum-mut이 언급했듯이, 그 중 하나에 버그가 있습니다(물론 SO 커뮤니티는 그것에 대한 수정 사항을 제공했습니다).Microsoft의 내부 우선 순위 버그대기열 <T>?

저는 줄리언 벅널의 블로그에서 여기서 하나를 찾았습니다 - http://www.boyet.com/Articles/PriorityQueueCSharp3.html

우리는 대기열의 우선순위가 낮은 항목들이 시간이 지남에 따라 결국 최상위로 '거품이 되어' 굶주림을 겪지 않도록 약간 수정했습니다.

이 구현이 유용할 수 있습니다. 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;
    }
}

만만하다.

알고 키트

저는 NuGet을 통해 이용할 수 있는 AlgoKit라는 오픈 소스 라이브러리를 작성했습니다.포함되는 항목:

• 암시적 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);

왜 저 세 무더기야?

라킨, 센 및 타잔이 우선순위 대기열에 대한 기초적인 경험적 연구, arXiv:1403.0252v1 [cs]에서 보여주듯이 최적의 구현 선택은 입력에 크게 의존합니다.DS] 그들은 암묵적인 d-ary 힙, 페어링 힙, 피보나치 힙, 이항 힙, 명시적인 d-ary 힙, 순위 페어링 힙, 지진 힙, 위반 힙, 순위 완화 약한 힙 및 엄격한 피보나치 힙을 테스트했습니다.

AlgoKit은 테스트된 힙 중 가장 효율적인 것으로 보이는 3가지 유형의 힙을 특징으로 합니다.

선택에 대한 힌트

상대적으로 적은 수의 원소의 경우 암시적 힙, 특히 4차 힙(암묵적 4-ary)을 사용할 수 있습니다.더 큰 힙 크기에서 작동하는 경우 이항 힙 및 쌍 힙과 같은 상각 구조가 더 나은 성능을 발휘해야 합니다.

단순 최대 힙 구현.

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

Java 구현(java.util)에서 Java to C# 변환기를 사용합니다.우선 순위.큐)는 Java Collections 프레임워크에서 또는 알고리즘과 코어 코드를 보다 지능적으로 사용하여 C# Collections 프레임워크 API for Queues 또는 최소한 Collections를 준수하는 자체 제작의 C# 클래스에 플러그인합니다.

다음은 엔제네릭 팀의 또 다른 구현입니다.

NGenerics 우선 순위대기열

저는 최근에 같은 문제를 겪었고 결국 이것을 위한 NuGet 패키지를 만들었습니다.

이렇게 하면 표준 힙 기반 우선 순위 대기열이 구현됩니다.또한 BCL 컬렉션의 모든 일반적인 세부 사항을 갖추고 있습니다.ICollection<T>그리고.IReadOnlyCollection<T>구현, 사용자 정의IComparer<T>지원, 초기 용량 지정 기능 및DebuggerTypeProxy디버거에서 컬렉션을 더 쉽게 작업할 수 있습니다.

프로젝트에 .cs 파일 하나만 설치하는 패키지의 인라인 버전도 있습니다(외부에서 볼 수 있는 종속성을 사용하지 않으려는 경우에 유용합니다.

자세한 내용은 github 페이지에서 확인할 수 있습니다.

의 다음 구현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; } }
    }
}

언급URL : https://stackoverflow.com/questions/102398/priority-queue-in-net