.Net中的优先队列

我正在寻找一个优先级队列或堆数据结构的.NET实现

优先级队列是比简单sorting更灵活的数据结构，因为它们允许新元素以任意间隔进入系统。 将新工作插入优先级队列要比在每次到达时重新sorting所有内容要便宜得多。

基本优先级队列支持三个主要操作：

• 插入（Q，X）。 给定一个具有密钥k的项目x，将其插入优先级队列Q.
• 查找-最小（Q）。 返回指向其优先级队列Q中的键值小于其他键的项的指针。
• 删除 – 最小（Q）。 从优先级队列Q中删除其项最小的项

除非我看错了地方，否则框架中没有一个。 有人知道一个好的，还是应该滚我自己的？

Answer 1

我喜欢在PowerCollections中使用OrderedBag和OrderedSet类作为优先级队列。

Answer 2

您可能会喜欢C5通用收集库中的 IntervalHeap。 引用用户指南

Class IntervalHeap<T>使用以对数组forms存储的间隔堆来实现接口IPriorityQueue<T> 。 FindMin和FindMax操作以及索引器的get-accessor花费时间O（1）。 DeleteMin，DeleteMax，Add和Update操作以及索引器的set-accessor花费时间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/安装;

Answer 3

这是我在.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; } } 

一些testing：

 [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)); } } 

Answer 4

这里有一个我刚刚写的，也许它不是最优化（只是使用一个sorting字典），但很容易理解。 你可以插入不同types的对象，所以没有通用的队列。

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

Answer 5

我在他的博客上find了Julian Bucknall的一个 – http://www.boyet.com/Articles/PriorityQueueCSharp3.html

我们稍微修改了一下，这样队列中的低优先级项目最终会随时间推移到顶端，所以它们不会遭受饥饿。

Answer 6

你可能会发现有用的这个实现： http : //www.codeproject.com/Articles/126751/Priority-queue-in-Csharp-with-help-of-heap-data-st.aspx

它是通用的，并基于堆数据结构

Answer 7

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

简单。

Answer 8

在Java Collections框架中的Java实现（java.util.PriorityQueue）上使用Java to C＃转换器，或者更智能地使用algorithm和核心代码，并将其插入到自己的C＃类中，使其符合C＃集合框架队列API或至less集合。

Answer 9

正如Microsoft Collections for .NET所述 ，Microsoft在.NET Framework中编写了2个内部的PriorityQueue类 （在线共享）。 他们的代码可以试用。

编辑：作为@ mathusum-mut评论说，有一个在微软的内部PriorityQueue类（SO社区，当然，提供了修补程序）之一的错误 ： 在微软的内部PriorityQueue <T>的错误？

Answer 10

这是NGenerics团队的另一个实现：

NGenerics PriorityQueue

Answer 11

我最近有同样的问题，最终创build了一个NuGet包 。

这实现了一个标准的基于堆的优先级队列。 它还具有BCL集合的所有常见细节： ICollection<T>和IReadOnlyCollection<T>实现，自定义IComparer<T>支持，指定初始容量的能力以及一个DebuggerTypeProxy ，使集合更容易处理debugging器。

还有一个Inline版本的软件包，它只是将一个.cs文件安装到你的项目中（如果你想避免使用外部可见的依赖项）。

有关更多信息，请访问github页面 。

Answer 12

一个简单的最大堆实现。

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

Answer 13

AlgoKit

我写了一个名为AlgoKit的开源库，可以通过NuGet获得 。 它包含：

• 隐式d-ary堆 （ArrayHeap），
• 二项式堆 ，
• 配对堆 。

代码已被广泛testing。 我绝对推荐你试试看。

例

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

为什么这三堆？

实施的最佳select是强烈依赖input的，正如Larkin，Sen和Tarjan在优先队列的回归基础实证研究 arXiv：1403.0252v1 [cs.DS]中所表明的那样 。 他们testing了隐含的d-ary堆，配对堆，斐波那契堆，二项堆，显式堆栈，排列堆，地震堆，违反堆，排名松散的弱堆和严格的Fibonacci堆。

AlgoKit具有三种types的堆，这些堆在testing中似乎是最有效的。

提示select

对于相对较less的元素，您可能有兴趣使用隐式堆，特别是四元堆（隐式4元）。 如果在较大的堆大小上运行，像二项堆和配对堆这样的摊销结构应该performance得更好。

Answer 14

下面的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; } } } }