В .NET 6 появилась новая коллекция — PriorityQueue<TElement,TPriority>. До этого очереди с приоритетами уже были в .NET, но только в виде внутренних классов — они использовались под капотом разных механизмов в WPF, Rx.NET и в других частях фреймворка.
Но в .NET 6 PriorityQueue стала новой коллекцией, которой теперь можно пользоваться из клиентского кода. Давайте посмотрим, что предлагает эта очередь, как она устроена внутри и насколько быстро работает. Под катом будет постепенное погружение: от примеров использования в коде к введению n-арные деревья.
Что это такое
PriorityQueue — это коллекция элементов, каждый из которых имеет значение и приоритет. Элементы добавляются в очередь с определенным приоритетом и извлекаться из неё “последовательно” — вначале будут извлечены элементы с наименьшим приоритетом, добавленные первыми. То есть, PriorityQueue — это модификация обычной FIFO (first-in-first-out) очереди, в которой элементы с меньшим приоритетом будут оказываться перед всеми элементами с большим приоритетом и извлекаться первыми.
В каких задачах может пригодиться PriorityQueue? Если коротко, то в тех же, что и обычная очередь, когда часть элементов нужно обработать “вне очереди”. С большой вероятностью такой сценарий понадобится как часть инфраструктурного кода. Вот пара примеров использования PriorityQueue:
- Организация очереди обработки запросов веб-сервером, в которой входящие запросы из Lisnter’а складываются в очередь и приоритезириуются на основе оставшегося лимита времени запроса или явного приоритета запроса (запрос демона или запрос фронта).
- Алгоритм Дейкстры — если пишите логистический сервис или просто ищите путь в графе обработчиков в вашем workflow (а это может быть и вывод правил в экспертных системах, и парсинг сайтов/данных).
- Любая абстрактная система асинхронной обработки данных/событий/запросов, в которой может быть класс обслуживания — например, если вы хотите дать возможность выполнить в своей системе какой-то служебный запрос перед всеми на случай забитой очереди.
Как работает PriorityQueue
Обычная очередь извлекает элементы в порядке их добавления — first in first out. Очередь с приоритетами извлекает элементы в порядке приоритета от меньшего к большему и также реализует first in first out для элементов с одинаковым приоритетом:
Вывод на консоль:
Как PriorityQueue сравнивает приоритеты
Чтобы определить наименьший приоритет нужно как-то сравнивать приоритеты между собой. PriorityQueue использует для этого стандартный интерфейс IComparer<T>:
По умолчанию используется дефолтный компоратор System.Collections.Generic.Comparer<TPriority>.Default. Если приоритет задается сложным типом (например, классом ServerHealthState), то можно передать в конструктор PriorityQueue свою реализацию компоратора:
Контракт PriorityQueue
Создать новый экземпляр PriorityQueue можно тремя способами: инициализировать пустую очередь, задать начальное количество элементов чтобы избежать дополнительного расширения массива при добавлении новых элементов или инициализировать очередь готовым набором значений с приоритетом:
Каждый конструктор имеет перегрузку с компаратором в качестве дополнительного элемента:
Интересной особенностью очереди с приоритетом является то, что в случае пустой очереди начальное хранилище оказывается пустым и расширяется до 4 элементов при первом добавлении:
У PriorityQueue есть несколько свойств для получения информации об очереди:
Новые элементы можно добавить либо по одному, либо сразу множеством — с общим приоритетом или отдельным значением приоритета для каждого элемента:
Кроме извлечения очередного элемента из очереди есть привычный метод Peek, который получает элемент из очереди, не удаляя его. В случае с пустой очередью попытка извлечения элемента закончится исключением InvalidOperationException, для безопасного извлечения есть аналогичные методы с префиксом Try:
Можно быстро очистить очередь при помощи метода Clear:
Есть и несколько специализированных методов, которые можно использовать для увеличения эффективности работы с очередью — быстро расширить внутреннее хранилище до определенного значения, обрезать внутреннее хранилище или одновременно извлечь элемент и добавить новый:
Что внутри PriorityQueue
Как устроена очередь с приоритетами внутри?
Самая простая реализация “в лоб”, которую можно придумать — это связный список элементов. Новые элементы добавляются в хвост списка за константное время, а при извлечении нужно найти первый элемент с наименьшим приоритетом, перебрав для этого все элементы за линейное время. Peek тоже будет линейным.
Можно ли сделать извлечение элементов быстрее, чем O(n)? Для этого понадобится держать список в отсортированном упорядоченном состоянии. Если мы используем в качестве структуры данных связный список, то для добавления понадобится последовательно перебирать элементы в поиске нужного места для вставки и асимптотика Enqueue будет O(n), так что теперь добавление в очередь становится слишком дорогостоящей операцией. Если заменять список на динамический массив, то вставка потребует “развигания” элементов и всё равно останется O(n)-операцией.
На самом деле, для решения задачи хранения элементов с приоритетом, “быстрого” добавления новых элементов и извлечения первого элемента с наименьшим приоритетом идеально подходит такая структура данных, как куча. Есть несколько типов универсальных куч, а ещё специализированные кучи, которые предоставляют дополнительную функциональность или работают эффективнее, но имеют ограничения. Например, в качестве типа приоритета могут использоваться только целочисленные значения.
Чаще всего в библиотеках разных языков программирования используются универсальные кучи — бинарные или d-арные. Во-первых, они позволяют извлекать и добавлять элемент за O(log n), а, во-вторых, благодаря свойствам кучи для их хранения достаточно массива элементов. Навигация между родительскими и дочерними элементами для каждого узла происходит по простым формулам.
В .NET 6 в основе PriorityQueue лежит 4-арная min-куча (то есть куча, где каждый узел может иметь 4 элемента уровнем ниже и содержит минимальный элемент своего поддерева), представленная в виде массива кортежей (TElement Element, TPriority Priority)[] _nodes, которая инициализируются пустым массивом по-умолчанию и расширяется при недостаточном Capacity по стандартному правилу List<T> — в 2 раза, но не менее, чем на 4 элемента.
4-арная min-куча всегда удовлетворяет двум свойствам:
- Свойство формы: 4-арная куча — это полное 4-арное дерево, то есть такое дерево, где все уровни полностью заполнены, за исключением, возможно, последнего уровня. Узлы заполняются слева направо.
- Свойство кучи: значение (приоритета), хранящееся в каждом узле, меньше или равно его дочерним элементам.
Сложность операций в PriorityQueue связана с сложностью операций в куче:
- Enqueue(TElement, TPriority): O(log4 N)
- Dequeue(): O(log4 N)
- Peek(): O(1)
- Count: O(1)
Читать словесное описание алгоритмов кучи — сомнительное удовольствие, а иллюстрации для 4-арной кучи не прибавляют понятности, поэтому иллюстрации к алгоритмам будут на основе биарной min-кучи, а в примерах кода можно увидеть, что работа бинарной и 4-арной кучи отличается только методами навигации по куче, то есть получения индекса родительского и дочерних элементов.
Методы для навигации по куче в PriorityQueue:
Enqueue
Чтобы добавить элемент в кучу, нужно выполнить операцию увеличения кучи (есть разные термины: up-heap, bubble-up, heapify-up):
- Если куча пуста, то новый элемент становится её корнем (root).
- Добавляем новый элемент на нижний уровень кучи в первое доступное место.
- Сравниваем добавленный элемент с его родителем. Если они в правильном порядке, то операция завершена.
- Если нет, то меняем добавленный элемент с родительским элементом местами и возвращаемся к предыдущему шагу.
Количество требуемых операций зависит только от количества уровней, на которые должен подняться новый элемент чтобы привести кучу в согласованное состяоние.
Итоговая временная сложность в худшем случае составляет O(log N), а в случаях, когда количество элементов значительно превышает количество различных возможных приоритетов — средняя сложность будет стремиться к О(1).
Dequeue
Для извлечения минимального значения из min-heap достаточно обратиться к _nodes[0]. Алгоритм удаления корневого (минимального) элемента из кучи:
- Удаляем значение корневого элемента
- Заменяем текущий удаляемый (корневой) элемент последним элементом кучи (_nodes[0] = _nodes[_size - 1];
- Сравниваем текущий элемент с его потомками. Если они не в правильном порядке (то есть, существуют потомки меньше текущего элемента), то меняем текущий элемент с наименьшим из потомков и повторяем шаг.
- Если они в правильном порядке, то операция завершена.
На примере бинарного min-дерева из иллюстрации после извлечения значения [0]-го элемента на его место встает последний ([14]-ый). Из потомков [1]-го и [2]-го выбирается наименьший — [2]-ой, т.к. приоритет [0]-го 26, а [2]-го 18, то они заменяются местами, а [2]-ой элемент становится текущим. Затем из его потомков, [5]-го и [6]-го элементов выбирается тот, у которого приоритет ниже, это [6]-ой элемент. Так как приоритет [2]-го теперь 26, а [6]-го 22, то они меняются местами, а [6]-ой элемент становится текущим. Теперь у текущего элемента только 1 потомок, [13]-ый. Его приоритет выше, чем приоритет текущего, поэтому алгоритм заканчивается.
В PriorityQueue есть пара интересных оптимизаций. Например, при добавлении множества элементов с помощью public void EnqueueRange(IEnumerable<(TElement Element, TPriority Priority)> items!!), фактически коллекция копируется в исходном виде в _nodes, а уже потом массив _nodes один раз перестраивается в кучу с помощью приватного метода Heapify, что позволяет получить итоговую сложность O(log4 N) вместо O(k * log4 N), где k — количество добавляемых элементов.
Метод EnqueueDequeue сравнивает добавляемый элемент с текущим корневым элементов. Если добавляемый элемент имеет меньший приоритет, то он сразу будет извлечен и перестроения кучи не понадобится, а если нет — то вместо двух перестроений для извлечения и добавления элемента понадобится только одно:
Да кто такой этот ваш UnorderedItemsCollection
У новой PriorityQueue есть свойство, которое возвращает элементы очереди в неупорядоченном виде. Но возвращает свойство не массив или енумератор, а вложенный в очередь тип UnorderedItemsCollection. Всё из-за специального енумератора, который отслеживает, что очередь не изменилась во время перебора (не изменилась переменная _version, а перечисление не вышло за пределы очереди) поскольку внутренний массив содержит capacity элементов, а не _size элементов.
Итератор перебирает элементы внутреннего представления кучи _nodes, так что говорить, что UnorderedItemsCollection действительно Unordered не совсем правильно. На самом деле, итератор будет всегда упорядочен в соответствии с правилами хранения 4-арной min-кучи в массиве.
(Очевидные?) ограничения
TPriority может быть любым типом, в том числе изменяемым. Можно, например, сделать такую очередь:
И очередь перестраивает кучу при каждой операции. Но, например, при извлечении элемента куча будет перестраиваться только после извлечения элемента с минимальным приоритетом, даже если приоритет другого элемента изменился и стал минимальным:
При добавлении нового элемента куча перестраивается только до уровня, который нужен добавляемому элементу и всё ломается ещё сильнее:
Поэтому ну их изменяемые приоритеты, лучше используйте для TPriority что-нибудь иммутабельное.
Хорошая новость об этом ограничении: в план работ по .NET 7 добавлен issue, позволяющий работать с элементами с изменяемым приоритетом.
