Приоритетная очередь в .Net

Возможный дубликат:
приоритетная очередь в .Net

Этот вопрос аналогичен, но я хочу точно знать:

Есть ли класс / структура / ... в .Net для очереди приоритетов? Как и в STL, где для этого есть priority_queue. Он принимает функцию сравнения для поддержки настраиваемых сортировок.

Лучшее, что я нашел в .Net, - это SortedList ‹Key, Value›, который сортирует значения по ключу. Таким образом, одним из решений является реализация настраиваемого интерфейса Сравнить для класса Key. Но я не могу разделить свои элементы на пары ключ / значение. У меня есть атомарные элементы, которые должны быть поставлены в очередь в соответствии с их значениями с помощью настраиваемой функции.

Итак, есть ли в .Net какой-либо класс коллекции, который принимает функцию сравнения для сортировки элементов it?

Есть ли способ получить класс .Net (возможно, HashSet), поддерживающий эту функцию?

Примечание:

  • Я знаю, что многие сторонние разработчики реализовали для этого действительно хорошие классы. Может быть, хорошим примером является PowerCollections. Но я хочу быстрое и простое решение с использованием существующих классов в .Net
  • Я использую .Net Framework 3.5

.net c# priority-queue
person Isaac    schedule 26.10.2009    source источник
comment
По состоянию на январь 2021 года в .Net Core добавлена ​​реализация PriorityQueue. Фактическую фиксацию репо и API можно найти здесь: github.com/dotnet/runtime/ совершить /   -  person Daniel    schedule 24.02.2021

Ответы (2)


arrow_upward
3
arrow_downward

Вы можете использовать общий класс SortedDictionary.

Вы можете указать объект сравнения для конструктора, который должен обрабатывать приоритетное сравнение ваших объектов:

public class DataComparer : IComparer<Data>
{
    public Int32 Compare(Data a, Data b)
    {
        if (a == null && b == null)
            return 0;
        if (a == null)
            return -1;
        if (b == null)
            return +1;
        return a.Priority.CompareTo(b.Priority);
    }
}

SortedDictionary<Data, Data> priQueue = new SortedDictionary<Data, Data>(
    new DataComparer());
person Lasse V. Karlsen    schedule 26.10.2009
comment
Кажется, мне нужно дважды сохранить свой элемент (класс Data). Как я уже сказал, у меня нет пары ключ / значение. У меня есть атомарные элементы из Data и Compare функция / класс / ... - person Isaac; 26.10.2009
comment
Не имеет значения, является ли класс Data на самом деле классом, это всего лишь ссылка, которую вы сохраняете дважды. Вы, конечно, можете обернуть эту коллекцию в одну из своих, предоставляя более компактный интерфейс для ваших нужд. - person Lasse V. Karlsen; 26.10.2009
comment
Спасибо за сниппет Лассе, отвлекся на менеджера :) - person Russ Clarke; 26.10.2009
comment
Разве это не подведет, если приоритеты будут равны? - person Mechanical snail; 08.11.2012

arrow_upward
1
arrow_downward

Вы можете просто реализовать IComparable в своем классе и создать конкретный компаратор внутри своего класса, чтобы вы могли просто использовать IList.Sort ()?

person Russ Clarke    schedule 26.10.2009
comment
Это решение действительно работает, но имеет слабую производительность. Когда я вставляю / удаляю элемент в / из списка, отсортированный список будет разрушен, и поскольку IList.Sort () не умен, мне придется делать больше, чем обычный priority_queue - person Isaac; 26.10.2009
comment
В этом случае не используйте IList, а реализуйте ICollection, и вы можете указать свой собственный метод Insert, который позволяет правильно упорядочивать при вставке. - person Russ Clarke; 26.10.2009
comment
@Ress C - 'ICollection' класса 'List'? Или используя другой класс? вы можете предоставить простой псевдокод? Большое спасибо! - person Isaac; 26.10.2009