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()
    {
    }
}

我见过的所有实现都假设 item 是一个 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屋！