我正在寻找优先级队列或堆数据结构的.NET实现
Priority queues are data structures that provide more flexibility than simple sorting, because they allow new elements to enter a system at arbitrary intervals. It is much more cost-effective to insert a new job into a priority queue than to re-sort everything on each such arrival.
The basic priority queue supports three primary operations:
Insert(Q,x). Given an item x with key k, insert it into the priority queue Q.
Find-Minimum(Q). Return a pointer to the item
whose key value is smaller than any other key in the priority queue
Q.
Delete-Minimum(Q). Remove the item from the priority queue Q whose key is minimum
除非我找错地方了，否则框架里没有。有谁知道好的吗，还是我自己卷?
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;
}
}
一件容易的事。
你可能会喜欢C5泛型集合库中的IntervalHeap。引用用户指南
类IntervalHeap<T>使用存储为对数组的间隔堆实现接口IPriorityQueue<T>。FindMin和
FindMax操作和索引器的get-访问器花费的时间为O(1)。DeleteMin,
DeleteMax、Add和Update操作，以及索引器的集访问器，都需要时间
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/安装
下面的PriorityQueue实现使用了System库中的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; } }
}
}
AlgoKit
我写了一个名为AlgoKit的开源库，可以通过NuGet获得。它包含:
隐式d-ary堆(ArrayHeap)，
二项堆,
配对堆。
代码已经经过了广泛的测试。我强烈建议你试一试。
例子
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具有三种类型的堆，在测试中似乎是最有效的。
关于选择的提示
对于数量相对较少的元素，您可能会对使用隐式堆感兴趣，特别是第四元堆(隐式4元)。在操作较大堆大小的情况下，像二项式堆和配对堆这样的平摊结构应该执行得更好。
