Вы можете добавить проверки безопасности, а что нет, но вот очень простая реализация, использующая 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 реализован внутри как двоичное дерево.
В приведенной выше реализации требуются следующие вспомогательные классы. Это адрес комментария Лассе В. Карлсена о том, что элементы с одинаковым приоритетом не могут быть добавлены с использованием простой реализации с использованием 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);
}
}
}