mpe*_*pen 7 c# queue data-structures
我正在寻找一个具有如下界面的优先级队列:
class PriorityQueue<T>
{
public void Enqueue(T item, int priority)
{
}
public T Dequeue()
{
}
}
我见过的所有实现都假设这item是一个IComparable但我不喜欢这种方法; 我想在将其推入队列时指定优先级.
如果不存在现成的实现,那么自己做这个的最佳方法是什么？我应该使用什么底层数据结构？某种自平衡树,还是什么？标准的C#.net结构会很好.
ito*_*son 11
如果您有基于IComparable的现有优先级队列实现,则可以轻松地使用它来构建所需的结构:
public class CustomPriorityQueue<T> // where T need NOT be IComparable
{
private class PriorityQueueItem : IComparable<PriorityQueueItem>
{
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<PriorityQueueItem> _inner = new PriorityQueue<PriorityQueueItem>();
public void Enqueue(T item, int priority)
{
_inner.Enqueue(new PriorityQueueItem(item, priority));
}
public T Dequeue()
{
return _inner.Dequeue().Item;
}
}
您可以添加安全检查,但不是,但这是一个非常简单的实现,使用SortedList:
class PriorityQueue<T> {
SortedList<Pair<int>, T> _list;
int count;
public PriorityQueue() {
_list = new SortedList<Pair<int>, T>(new PairComparer<int>());
}
public void Enqueue(T item, int priority) {
_list.Add(new Pair<int>(priority, count), item);
count++;
}
public T Dequeue() {
T item = _list[_list.Keys[0]];
_list.RemoveAt(0);
return item;
}
}
我假设较小的值priority对应于较高优先级的项目(这很容易修改).
如果多个线程将访问队列,您还需要添加锁定机制.这很简单,但如果您需要这里的指导,请告诉我.
SortedList 在内部实现为二叉树.
上面的实现需要以下帮助器类.这解决了Lasse V. Karlsen的评论,即使用a的naive实现无法添加具有相同优先级的项目SortedList.
class Pair<T> {
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<T> pair = other as Pair<T>;
if (pair == null) {
return false;
}
return (this.First.Equals(pair.First) && this.Second.Equals(pair.Second));
}
}
class PairComparer<T> : IComparer<Pair<T>> where T : IComparable {
public int Compare(Pair<T> x, Pair<T> 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);
}
}
}
您可以围绕一个现有实现编写一个包装器,根据您的偏好修改接口:
using System;
class PriorityQueueThatYouDontLike<T> where T: IComparable<T>
{
public void Enqueue(T item) { throw new NotImplementedException(); }
public T Dequeue() { throw new NotImplementedException(); }
}
class PriorityQueue<T>
{
class ItemWithPriority : IComparable<ItemWithPriority>
{
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<ItemWithPriority> q = new PriorityQueueThatYouDontLike<ItemWithPriority>();
public void Enqueue(T item, int priority)
{
q.Enqueue(new ItemWithPriority(item, priority));
}
public T Dequeue()
{
return q.Dequeue().Item;
}
}
这与itowlson的建议相同.我花了更长的时间来写我的,因为我填写了更多的方法.:-s
这是一个非常简单的轻量级实现,它具有推送和弹出的O(log(n))性能.它使用构建在List <T>之上的堆数据结构.
/// <summary>Implements a priority queue of T, where T has an ordering.</summary>
/// 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.
/// <typeparam name="T">Type T, should implement IComparable[T];</typeparam>
public class PriorityQueue<T> where T : IComparable<T> {
/// <summary>Clear all the elements from the priority queue</summary>
public void Clear () {
mA.Clear ();
}
/// <summary>Add an element to the priority queue - O(log(n)) time operation.</summary>
/// <param name="item">The item to be added to the queue</param>
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
}
}
/// <summary>Returns the number of elements in the queue.</summary>
public int Count {
get { return mA.Count; }
}
/// <summary>Returns true if the queue is empty.</summary>
/// 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; }
}
/// <summary>Allows you to look at the first element waiting in the queue, without removing it.</summary>
/// This element will be the one that will be returned if you subsequently call Next().
public T Peek () {
return mA[0];
}
/// <summary>Removes and returns the first element from the queue (least element)</summary>
/// <returns>The first element in the queue, in ascending order.</returns>
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;
}
/// <summary>The List we use for implementation.</summary>
List<T> mA = new List<T> ();
}
这是我高度优化的 C# priority-queue使用的确切接口。
它是专门为寻路应用程序（A* 等）开发的，但也适用于任何其他应用程序。
public class User
{
public string Name { get; private set; }
public User(string name)
{
Name = name;
}
}
...
var priorityQueue = new SimplePriorityQueue<User>();
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();