プライオリティ キューまたはヒープ データ構造の .NET 実装を探しています
プライオリティ キューは、任意の間隔で新しい要素をシステムに入力できるため、単純な並べ替えよりも柔軟性が高いデータ構造です。新しいジョブを優先キューに挿入する方が、そのような到着ごとにすべてを再ソートするよりもはるかに費用対効果が高くなります。
基本プライオリティ キューは、次の 3 つの主要な操作をサポートしています。
- 挿入 (Q,x)。キー k を持つアイテム x が与えられた場合、それを優先キュー Q に挿入します。
- Find-Minimum(Q)。優先度キュー Q 内の他のどのキーよりもキー値が小さい項目へのポインターを返します。
- 最小削除 (Q)。キーが最小の優先度キュー Q からアイテムを削除します
私が間違った場所を探していない限り、フレームワークにはありません。誰かが良いものを知っていますか、それとも自分でロールする必要がありますか?
C5 Generic Collection Libraryの IntervalHeap が好きかもしれません。ユーザーガイドを引用するには
クラスは、ペアの配列として格納された間隔ヒープを使用して
IntervalHeap<T>インターフェイスを実装します。and 操作、およびインデクサーIPriorityQueue<T>のget-accessor には O(1) の時間がかかります。、、 Add および Update 操作、およびインデクサーの set-accessor には、O(log n) の時間がかかります。通常のプライオリティ キューとは対照的に、インターバル ヒープは最小と最大の両方の操作を同じ効率で提供します。FindMinFindMaxDeleteMinDeleteMax
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));
}
}
私は、 PowerCollectionsOrderedBagのおよびOrderedSetクラスを優先キューとして使用するのが好きです。
これが私が書いたものです。おそらくそれは最適化されていない（ソートされた辞書を使用しているだけです）が、理解するのは簡単です。さまざまな種類のオブジェクトを挿入できるため、汎用キューはありません。
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
キューにある優先度の低いアイテムが時間の経過とともに最終的に「バブルアップ」し、飢餓に苦しむことがないように、少し修正しました。
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;
}
}
簡単。
この実装が役立つ場合があります：http： //www.codeproject.com/Articles/126751/Priority-queue-in-Csharp-with-help-of-heap-data-st.aspx
これは一般的で、ヒープデータ構造に基づいています
NuGetから入手できるAlgoKitというオープン ソース ライブラリを作成しました。を含む：
コードは広範囲にテストされています。ぜひ試してみることをお勧めします。
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 ヒープ、ペアリング ヒープ、フィボナッチ ヒープ、二項ヒープ、明示的な d-ary ヒープ、ランク ペアリング ヒープ、地震ヒープ、違反ヒープ、ランク緩和された弱いヒープ、厳密なフィボナッチ ヒープをテストしました。
AlgoKit は、テストした中で最も効率的であると思われる 3 種類のヒープを備えています。
要素の数が比較的少ない場合は、暗黙のヒープ、特に 4 進ヒープ (暗黙の 4 進) の使用に関心がある可能性があります。より大きなヒープ サイズで操作する場合は、二項ヒープやペアリング ヒープなどの償却された構造の方がパフォーマンスが向上します。
Java Collections フレームワークの Java 実装 (java.util.PriorityQueue) で Java から C# へのトランスレータを使用するか、よりインテリジェントにアルゴリズムとコア コードを使用して、C# Collections フレームワークに準拠する独自に作成した C# クラスにプラグインします。キュー、または少なくともコレクションの API。
NGenerics チームによる別の実装を次に示します。
次の a の実装では、System ライブラリ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; } }
}
}