C＃优先级队列

我正在寻找一个具有如下界面的优先级队列：

class PriorityQueue { public void Enqueue(T item, int priority) { } public T Dequeue() { } } 

我见过的所有实现都假设该item是IComparable但我不喜欢这种方法; 我想在将其推入队列时指定优先级。

如果不存在现成的实现，那么自己做这个的最佳方法是什么？ 我应该使用什么底层数据结构？ 某种自平衡树，还是什么？ 标准的C＃.net结构会很好。

Answer 1

如果您有基于IComparable的现有优先级队列实现，则可以轻松地使用它来构建所需的结构：

 public class CustomPriorityQueue // where T need NOT be IComparable { private class PriorityQueueItem : IComparable { private readonly T _item; private readonly int _priority: // obvious constructor, CompareTo implementation and Item accessor } // the existing PQ implementation where the item *does* need to be IComparable private readonly PriorityQueue _inner = new PriorityQueue(); public void Enqueue(T item, int priority) { _inner.Enqueue(new PriorityQueueItem(item, priority)); } public T Dequeue() { return _inner.Dequeue().Item; } } 

Answer 2

您可以添加安全检查，但不是，但这是一个使用SortedList的非常简单的实现：

 class PriorityQueue { SortedList, T> _list; int count; public PriorityQueue() { _list = new SortedList, T>(new PairComparer()); } public void Enqueue(T item, int priority) { _list.Add(new Pair(priority, count), item); count++; } public T Dequeue() { T item = _list[_list.Keys[0]]; _list.RemoveAt(0); return item; } } 

我假设较小的priority值对应于较高优先级的项目（这很容易修改）。

如果多个线程将访问队列，您还需要添加锁定机制。 这很简单，但如果您需要这里的指导，请告诉我。

SortedList在内部实现为二叉树。

上面的实现需要以下帮助器类。 这解决了Lasse V. Karlsen的评论，即使用SortedList使用朴素实现无法添加具有相同优先级的项目。

 class Pair { public T First { get; private set; } public T Second { get; private set; } public Pair(T first, T second) { First = first; Second = second; } public override int GetHashCode() { return First.GetHashCode() ^ Second.GetHashCode(); } public override bool Equals(object other) { Pair pair = other as Pair; if (pair == null) { return false; } return (this.First.Equals(pair.First) && this.Second.Equals(pair.Second)); } } class PairComparer : IComparer> where T : IComparable { public int Compare(Pair x, Pair y) { if (x.First.CompareTo(y.First) < 0) { return -1; } else if (x.First.CompareTo(y.First) > 0) { return 1; } else { return x.Second.CompareTo(y.Second); } } } 

Answer 3

您可以围绕一个现有实现编写一个包装器，该实现将接口修改为您的首选项：

 using System; class PriorityQueueThatYouDontLike where T: IComparable { public void Enqueue(T item) { throw new NotImplementedException(); } public T Dequeue() { throw new NotImplementedException(); } } class PriorityQueue { class ItemWithPriority : IComparable { public ItemWithPriority(T t, int priority) { Item = t; Priority = priority; } public T Item {get; private set;} public int Priority {get; private set;} public int CompareTo(ItemWithPriority other) { return Priority.CompareTo(other.Priority); } } PriorityQueueThatYouDontLike q = new PriorityQueueThatYouDontLike(); public void Enqueue(T item, int priority) { q.Enqueue(new ItemWithPriority(item, priority)); } public T Dequeue() { return q.Dequeue().Item; } } 

这与itowlson的建议相同。 我花了更长的时间来写我的，因为我填写了更多的方法。 ：-s

Answer 4

这是一个非常简单的轻量级实现，它具有推送和弹出的O（log（n））性能。 它使用构建在List 之上的堆数据结构 。

 /// 
Implements a priority queue of T, where T has an ordering.
 /// Elements may be added to the queue in any order, but when we pull /// elements out of the queue, they will be returned in 'ascending' order. /// Adding new elements into the queue may be done at any time, so this is /// useful to implement a dynamically growing and shrinking queue. Both adding /// an element and removing the first element are log(N) operations. /// /// The queue is implemented using a priority-heap data structure. For more /// details on this elegant and simple data structure see "Programming Pearls" /// in our library. The tree is implemented atop a list, where 2N and 2N+1 are /// the child nodes of node N. The tree is balanced and left-aligned so there /// are no 'holes' in this list. /// Type T, should implement IComparable[T]; public class PriorityQueue where T : IComparable { /// 
Clear all the elements from the priority queue
 public void Clear () { mA.Clear (); } /// 
Add an element to the priority queue - O(log(n)) time operation.
 /// The item to be added to the queue public void Add (T item) { // We add the item to the end of the list (at the bottom of the // tree). Then, the heap-property could be violated between this element // and it's parent. If this is the case, we swap this element with the // parent (a safe operation to do since the element is known to be less // than it's parent). Now the element move one level up the tree. We repeat // this test with the element and it's new parent. The element, if lesser // than everybody else in the tree will eventually bubble all the way up // to the root of the tree (or the head of the list). It is easy to see // this will take log(N) time, since we are working with a balanced binary // tree. int n = mA.Count; mA.Add (item); while (n != 0) { int p = n / 2; // This is the 'parent' of this item if (mA[n].CompareTo (mA[p]) >= 0) break; // Item >= parent T tmp = mA[n]; mA[n] = mA[p]; mA[p] = tmp; // Swap item and parent n = p; // And continue } } /// 
Returns the number of elements in the queue.
 public int Count { get { return mA.Count; } } /// 
Returns true if the queue is empty.
 /// Trying to call Peek() or Next() on an empty queue will throw an exception. /// Check using Empty first before calling these methods. public bool Empty { get { return mA.Count == 0; } } /// 
Allows you to look at the first element waiting in the queue, without removing it.
 /// This element will be the one that will be returned if you subsequently call Next(). public T Peek () { return mA[0]; } /// 
Removes and returns the first element from the queue (least element)
 /// The first element in the queue, in ascending order. public T Next () { // The element to return is of course the first element in the array, // or the root of the tree. However, this will leave a 'hole' there. We // fill up this hole with the last element from the array. This will // break the heap property. So we bubble the element downwards by swapping // it with it's lower child until it reaches it's correct level. The lower // child (one of the orignal elements with index 1 or 2) will now be at the // head of the queue (root of the tree). T val = mA[0]; int nMax = mA.Count - 1; mA[0] = mA[nMax]; mA.RemoveAt (nMax); // Move the last element to the top int p = 0; while (true) { // c is the child we want to swap with. If there // is no child at all, then the heap is balanced int c = p * 2; if (c >= nMax) break; // If the second child is smaller than the first, that's the one // we want to swap with this parent. if (c + 1 < nMax && mA[c + 1].CompareTo (mA[c]) < 0) c++; // If the parent is already smaller than this smaller child, then // we are done if (mA[p].CompareTo (mA[c]) <= 0) break; // Othewise, swap parent and child, and follow down the parent T tmp = mA[p]; mA[p] = mA[c]; mA[c] = tmp; p = c; } return val; } /// 
The List we use for implementation.
 List mA = new List (); } 

Answer 5

这是我高度优化的C＃优先级队列使用的确切接口。

它是专门为寻路应用程序（A *等）开发的，但也适用于任何其他应用程序。

唯一可能的问题是，为了挤出绝对最大性能，实现需要排队的值来扩展PriorityQueueNode 。

 public class User : PriorityQueueNode { public string Name { get; private set; } public User(string name) { Name = name; } } ... HeapPriorityQueue priorityQueue = new HeapPriorityQueue(MAX_USERS_IN_QUEUE); priorityQueue.Enqueue(new User("Jason"), 1); priorityQueue.Enqueue(new User("Joseph"), 10); //Because it's a min-priority queue, the following line will return "Jason" User user = priorityQueue.Dequeue(); 

Answer 6

这样的事情会怎么样？

 class PriorityQueue where TPriority : IComparable { private SortedList> pq = new SortedList>(); public int Count { get; private set; } public void Enqueue(TItem item, TPriority priority) { ++Count; if (!pq.ContainsKey(priority)) pq[priority] = new Queue(); pq[priority].Enqueue(item); } public TItem Dequeue() { --Count; var queue = pq.ElementAt(0).Value; if (queue.Count == 1) pq.RemoveAt(0); return queue.Dequeue(); } } class PriorityQueue : PriorityQueue { } 

Answer 7

我意识到你的问题特别要求一个非基于IComparable的实现，但我想指出Visual Studio Magazine最近的一篇文章。

http://visualstudiomagazine.com/articles/2012/11/01/priority-queues-with-c.aspx

@ itowlson的这篇文章可以给出完整的答案。

Answer 8

有点晚，但我会在这里添加它以供参考

https://github.com/ERufian/Algs4-CSharp

键值对优先级队列在Algs4 / IndexMaxPQ.cs，Algs4 / IndexMinPQ.cs和Algs4 / IndexPQDictionary.cs中实现

笔记：

1. 如果优先级不是IComparable，则可以在构造函数中指定IComparer
2. 入队的是一个索引及其优先级（对于原始问题，需要单独的List或T []来将该索引转换为预期结果，而不是将对象及其优先级排入队列。

Answer 9

看起来你可以用自己的队列编辑，每个优先级一个。 字典，只需将其添加到适当的一个。