Структура Данных Куча и Очередь с Приоритетом в .NET. Окончание
Начало
Согласно документации, тип PriorityQueue в .NET использует «четвертичную минимальную кучу на основе массива». Т.е. каждый узел в куче имеет 4 дочерних элемента.
Двоичные и d-арные кучи имеют несколько разные характеристики времени выполнения. Двоичные кучи немного быстрее удаляют корневой узел, а d-арные кучи быстрее выполняют некоторые другие операции. В целом, d-арные кучи, как правило, имеют более высокую производительность во время выполнения, чем двоичные кучи, из-за принципа работы кэширования памяти, поэтому их часто предпочитают.
PriorityQueue в .NET имеет множество методов, типичных для реализации очереди с приоритетом:
// создание с одновременным «упорядочиванием» в кучу
var queue = new PriorityQueue<string, int>([
("A", 15), ("B", 7), ("C", 23), ("D", 2), ("E", 22)
]);
// Поиск минимального элемента без извлечения
string peek = queue.Peek(); // "D"
// Извлечение минимального элемента
// Это приводит к удалению корня, поэтому
// куча должна быть «пересортирована»
string dequeue = queue.Dequeue(); // "D"
// Добавление элемента с приоритетом
// Скорее всего приводит к «пересортировке»
queue.Enqueue(element: "F", priority: 42);
// Добавление нескольких элементов
queue.EnqueueRange([("G", 3), ("H", 13)]);
// Одновременное извлечение и добавление нового элемента
// Т.к. для каждой операции требуется «пересортировка», это более эффективно, чем последовательный вызов Dequeue() и Enqueue()
string deque1 =
queue.DequeueEnqueue("I", 19); // "G"
// И наоборот
string deque2 =
queue.EnqueueDequeue("J", 31); // "H"
PriorityQueue имеет несколько других вспомогательных методов для контроля ее работы:
// Выдаёт элементы, не учитывая приоритет, позволяя их перечислить
var unordered = queue.UnorderedItems;
// Количество элементов
var count = queue.Count;
// Очистка очереди
queue.Clear();
// Позволяет задать компаратор для приоритета. По умолчанию это минимальная куча, следующий код создаёт максимальную кучу
var inverse = Comparer<int>
.Create((a, b) => 0 - a.CompareTo(b));
var maxQueue =
new PriorityQueue<string, int>(inverse);
// Уменьшает ёмкость массива, лежащего в основе кучи,
// если новая ёмкость меньше 90% от текущей
queue.TrimExcess();
Источник: https://andrewlock.net/an-introduction-to-the-heap-data-structure-and-dotnets-priority-queue/