C＃优先级队列 [英] C# Priority Queue

问题描述

我在寻找一个优先级队列，像这样的接口：

I'm looking for a priority queue with an interface like this:

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

    public T Dequeue()
    {
    }
}

我见过的所有实现假设项目是 IComparable的，但我不喜欢这种方法;我想指定，当我推到队列中的优先级。

All the implementations I've seen assume that item is an IComparable but I don't like this approach; I want to specify the priority when I'm pushing it onto the queue.

如果有现成的实施不存在，什么是去这样做这个自己的最佳方式？我应该使用什么底层的数据结构？某种自我平衡的树，还是什么？一个标准的C＃.NET结构将是很好的。

If a ready-made implementation doesn't exist, what's the best way to go about doing this myself? What underlying data structure should I use? Some sort of self-balancing tree, or what? A standard C#.net structure would be nice.

推荐答案

如果您有一个基于IComparable的现有优先级队列实现，你可以很容易地用它来建立你所需要的结构：

If you have an existing priority queue implementation based on IComparable, you can easily use that to build the structure you need:

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

这篇关于C＃优先级队列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！