C# 优先级队列

Question

我正在寻找具有如下接口(interface)的优先级队列:

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

    public T Dequeue()
    {
    }
}

我见过的所有实现都假设 item 是一个 IComparable 但我不喜欢这种方法；我想在将它插入队列时指定优先级。

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

Answer 1

如果您有一个基于 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;
  }
}