我正在寻找优先级队列或堆数据结构的.NET实现
优先级队列是比简单排序提供更多灵活性的数据结构,因为它们允许新元素以任意间隔进入系统.将新作业插入优先级队列比在每次到达时重新排序所有内容更具成本效益.
基本优先级队列支持三种主要操作:
插入(Q,X).给定具有密钥k的项x,将其插入优先级队列Q.
查找-最小(Q).返回指向其键值小于优先级队列Q中任何其他键的项的指针.
删除 - 最小(Q).从密钥最小的优先级队列Q中删除该项
除非我在错误的地方寻找,否则框架中没有一个.有人知道一个好的,或者我应该自己动手？
您可能喜欢C5 Generic Collection Library中的 IntervalHeap .引用用户指南
类使用存储为对数组的间隔堆
IntervalHeap实现接口IPriorityQueue.FindMin和FindMax操作以及索引器的get-accessor需要时间O(1).DeleteMin,DeleteMax,Add和Update操作以及索引器的set-accessor需要时间O(log n).与普通优先级队列相比,间隔堆以相同的效率提供最小和最大操作.
API很简单
> var heap = new C5.IntervalHeap(); > 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: IEnumerable { 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 Comparer { get; private set; } protected abstract bool Dominates(T x, T y); protected Heap() : this(Comparer .Default) { } protected Heap(Comparer comparer) : this(Enumerable.Empty (), comparer) { } protected Heap(IEnumerable collection) : this(collection, Comparer .Default) { } protected Heap(IEnumerable collection, Comparer 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 GetEnumerator() { return _heap.Take(Count).GetEnumerator(); } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } } public class MaxHeap : Heap { public MaxHeap() : this(Comparer .Default) { } public MaxHeap(Comparer comparer) : base(comparer) { } public MaxHeap(IEnumerable collection, Comparer comparer) : base(collection, comparer) { } public MaxHeap(IEnumerable collection) : base(collection) { } protected override bool Dominates(T x, T y) { return Comparer.Compare(x, y) >= 0; } } public class MinHeap : Heap { public MinHeap() : this(Comparer .Default) { } public MinHeap(Comparer comparer) : base(comparer) { } public MinHeap(IEnumerable collection) : base(collection) { } public MinHeap(IEnumerable collection, Comparer 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(new[] {9, 8, 4, 1, 6, 2, 7, 4, 1, 2});
AssertHeapSort(minHeap, minHeap.OrderBy(i => i).ToArray());
minHeap = new MinHeap { 7, 5, 1, 6, 3, 2, 4, 1, 2, 1, 3, 4, 7 };
AssertHeapSort(minHeap, minHeap.OrderBy(i => i).ToArray());
var maxHeap = new MaxHeap(new[] {1, 5, 3, 2, 7, 56, 3, 1, 23, 5, 2, 1});
AssertHeapSort(maxHeap, maxHeap.OrderBy(d => -d).ToArray());
maxHeap = new MaxHeap {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 heap, IEnumerable expected)
{
var sorted = new List();
while (heap.Count > 0)
sorted.Add(heap.ExtractDominating());
Assert.IsTrue(sorted.SequenceEqual(expected));
}
}
我喜欢使用PowerCollections中的OrderedBag和OrderedSet类作为优先级队列.
这是我刚写的一个,也许它不是优化的(只是使用排序的字典),但很容易理解.您可以插入不同类型的对象,因此没有通用队列.
using System;
using System.Diagnostics;
using System.Collections;
using System.Collections.Generic;
namespace PrioQueue
{
public class PrioQueue
{
int total_size;
SortedDictionary storage;
public PrioQueue ()
{
this.storage = new SortedDictionary ();
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
我们稍微对它进行了修改,以便队列中的低优先级项目最终会随着时间的推移"冒泡"到顶部,因此它们不会遭受饥饿.
您可能会发现这个实现很有用:http: //www.codeproject.com/Articles/126751/Priority-queue-in-Csharp-with-help-of-heap-data-st.aspx
它是通用的,基于堆数据结构
如Microsoft Collections for .NET中所述,Microsoft已在.NET Framework中编写(并在线共享)2个内部PriorityQueue类.他们的代码可以试用.
编辑:正如@ mathusum-mut评论的那样,微软内部的一个PriorityQueue类中存在一个错误(SO社区当然为它提供了修复):微软内部的PriorityQueue
class PriorityQueue{ IComparer comparer; T[] heap; public int Count { get; private set; } public PriorityQueue() : this(null) { } public PriorityQueue(int capacity) : this(capacity, null) { } public PriorityQueue(IComparer comparer) : this(16, comparer) { } public PriorityQueue(int capacity, IComparer comparer) { this.comparer = (comparer == null) ? Comparer .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; } }
简单.
京公网安备 11010802040832号 | 京ICP备19059560号-6 