.Net의 우선 순위 대기열 [닫힘]

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

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

기본 우선 순위 큐는 세 가지 기본 조작을 지원합니다.

  • 삽입 (Q, x). 키 k가있는 x 항목이 있으면 우선 순위 큐 Q에 삽입하십시오.
  • 최소값 찾기 (Q). 우선 순위 큐 Q의 다른 키보다 키 값이 작은 항목에 대한 포인터를 리턴하십시오.
  • 최소 삭제 (Q). 키가 최소 인 우선 순위 큐 Q에서 항목을 제거하십시오.

내가 틀린 곳을보고 있지 않는 한, 틀 안에는 없습니다. 누구든지 좋은 것을 알고 있습니까, 아니면 내 자신을 굴려야합니까?

답변

PowerCollections 의 OrderedBag및 OrderedSet클래스 를 우선 순위 대기열로 사용하는 것이 좋습니다.

답변

C5 Generic Collection Library 의 IntervalHeap을 좋아할 것 입니다. 사용 설명서 를 인용하려면

클래스 는 쌍의 배열로 저장된 간격 힙을 사용하여 IntervalHeap<T>인터페이스 IPriorityQueue<T>를 구현 합니다. FindMin 및 FindMax 작업과 인덱서의 get-accessor는 시간이 O (1)입니다. DeleteMin, DeleteMax, 추가 및 업데이트 작업 및 인덱서의 set 접근자는 시간이 O (log 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));
    }
}

답변

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

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

        }
    }
}

답변

Julian Bucknall이 자신의 블로그에서 http://www.boyet.com/Articles/PriorityQueueCSharp3.html을 찾았습니다 .

대기열의 우선 순위가 낮은 항목이 시간이 지남에 따라 맨 위로 ‘버블 업’되도록 기아를 약간 수정하여 기아가 발생하지 않도록했습니다.

답변

Microsoft Collections for .NET 에서 언급했듯이 Microsoft는 .NET Framework 내에서 2 개의 내부 PriorityQueue 클래스를 작성 (온라인 공유)했습니다 . 그들의 코드는 시험해 볼 수 있습니다.

편집 : @ mathusum-mut이 언급했듯이 Microsoft 내부 PriorityQueue 클래스 중 하나에 버그가 있습니다 (SO 커뮤니티는 물론 수정 사항을 제공했습니다). Microsoft 내부 PriorityQueue <T>의 버그?

답변

이 구현이 유용하다는 것을 알 수 있습니다 :
http://www.codeproject.com/Articles/126751/Priority-queue-in-Csharp-with-help-of-heap-data-st.aspx

일반적이며 힙 데이터 구조를 기반으로합니다.