.Net의 우선순위 큐
https://stackoverflow.com/questions/102398
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
우선순위 큐 또는 힙 데이터 구조의 .NET 구현을 찾고 있습니다.
우선순위 큐는 새로운 요소가 임의의 간격으로 시스템에 들어갈 수 있도록 하기 때문에 단순 정렬보다 더 많은 유연성을 제공하는 데이터 구조입니다.도착할 때마다 모든 것을 다시 정렬하는 것보다 우선 순위 대기열에 새 작업을 삽입하는 것이 훨씬 더 비용 효율적입니다.
기본 우선순위 큐는 세 가지 기본 작업을 지원합니다.
- (Q,x)를 삽입합니다.키 k가 있는 항목 x가 주어지면 이를 우선순위 큐 Q에 삽입합니다.
- 찾기-최소(Q).우선 순위 대기열 Q에서 키 값이 다른 키보다 작은 항목에 대한 포인터를 반환하십시오.
- 삭제-최소(Q).키가 최소인 우선순위 큐 Q에서 항목을 제거합니다.
내가 잘못된 곳을 찾고 있지 않는 한 프레임워크에는 아무 것도 없습니다.좋은 제품을 알고 있는 사람이 있나요? 아니면 제가 직접 굴려야 하나요?
해결책
나는 다음을 사용하는 것을 좋아한다. OrderedBag 그리고 OrderedSet 수업 파워컬렉션 우선순위 큐로.
다른 팁
IntervalHeap을 좋아할 수도 있습니다. C5 일반 컬렉션 라이브러리.인용하자면 사용자 설명서
수업
IntervalHeap<T>인터페이스 구현IPriorityQueue<T>쌍의 배열로 저장된 간격 힙을 사용합니다.FindMin 및 FindMax 작업 및 Indexer의 Get-Accessor는 시간을 보냅니다 (1).Deletemin, Deletemax, 추가 및 업데이트 작업 및 Indexer의 세트 액세서로 시간 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
대기열에 있는 우선순위가 낮은 항목이 결국 시간이 지남에 따라 맨 위로 '버블업'되어 기아 상태에 빠지지 않도록 이를 약간 수정했습니다.
에서 언급했듯이 .NET용 Microsoft 컬렉션, Microsoft는 작성하고 온라인으로 공유했습니다. 2개의 내부 PriorityQueue 클래스 .NET Framework 내에서.해당 코드를 시험해 볼 수 있습니다.
편집하다:@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
이는 일반적이며 힙 데이터 구조를 기반으로 합니다.
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 컬렉션 프레임워크의 Java 구현(java.util.PriorityQueue)에서 Java-C# 변환기를 사용하거나 보다 지능적으로 알고리즘과 핵심 코드를 사용하여 C# 컬렉션 프레임워크를 준수하는 자체 제작 C# 클래스에 연결합니다. 대기열용 API 또는 최소한 컬렉션용 API.
알고킷
나는 다음과 같은 오픈 소스 라이브러리를 작성했습니다. 알고킷, 다음을 통해 사용 가능 NuGet.여기에는 다음이 포함됩니다.
- 암시적 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);
왜 그 세 개의 힙이 있습니까?
최적의 구현 선택은 입력에 크게 좌우됩니다. Larkin, Sen 및 Tarjan이 보여주듯이 우선순위 큐에 대한 기본으로 돌아가는 실증적 연구, arXiv:1403.0252v1 [cs.DS].그들은 암시적 d-ary 힙, 페어링 힙, Fibonacci 힙, 이항 힙, 명시적 d-ary 힙, 순위 페어링 힙, quake 힙, 위반 힙, 순위 완화된 약한 힙 및 엄격한 Fibonacci 힙을 테스트했습니다.
AlgoKit에는 테스트된 것 중에서 가장 효율적인 것으로 보이는 세 가지 유형의 힙이 있습니다.
선택에 대한 힌트
상대적으로 적은 수의 요소의 경우 암시적 힙, 특히 4차 힙(암시적 4항)을 사용하는 데 관심이 있을 수 있습니다.더 큰 힙 크기에서 작동하는 경우 이항 힙 및 페어링 힙과 같은 상각 구조가 더 나은 성능을 발휘해야 합니다.
NGenerics 팀의 또 다른 구현은 다음과 같습니다.
나는 최근에 같은 문제가 있었고 결국 NuGet 패키지 이를 위해.
이는 표준 힙 기반 우선순위 큐를 구현합니다.또한 BCL 컬렉션의 일반적인 장점도 모두 갖추고 있습니다. ICollection<T> 그리고 IReadOnlyCollection<T> 구현, 사용자 정의 IComparer<T> 지원, 초기 용량을 지정하는 기능, DebuggerTypeProxy 디버거에서 컬렉션을 더 쉽게 작업할 수 있도록 합니다.
또한 인라인 단일 .cs 파일을 프로젝트에 설치하는 패키지 버전입니다(외부적으로 표시되는 종속성을 피하려는 경우 유용함).
자세한 내용은 다음에서 확인할 수 있습니다. 깃허브 페이지.
간단한 최대 힙 구현.
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; } }
}
}
