PriorityQueue в PascalABC.NET: очередь с приоритетами в .NET 10

Версия компилятора PascalABC.NET для .NET 10 позволяет напрямую использовать классы современной стандартной библиотеки .NET. Один из полезных примеров — PriorityQueue<TElement,TPriority> из пространства имён System.Collections.Generic.

Что такое очередь с приоритетами

Обычная очередь работает по принципу «первым пришёл — первым вышел». В очереди с приоритетами порядок извлечения определяется не временем добавления, а приоритетом элемента.

Рассмотрим очередь задач. Договоримся, что меньшее число означает более срочную задачу:

uses System.Collections.Generic;

begin
  var tasks := new PriorityQueue<string,integer>;

  tasks.Enqueue('Создать резервную копию',3);
  tasks.Enqueue('Обработать срочный запрос',1);
  tasks.Enqueue('Сформировать отчёт',2);

  while tasks.Count > 0 do
    Println(tasks.Dequeue);
end.

Результат:

Обработать срочный запрос
Сформировать отчёт
Создать резервную копию

Тип элемента и тип приоритета

В объявлении

PriorityQueue<string,integer>

string задаёт тип элементов очереди, а integer — тип их приоритетов. Элементы и приоритеты могут иметь и другие типы, если они подходят решаемой задаче.

Метод Enqueue добавляет элемент вместе с его приоритетом:

tasks.Enqueue('Обработать срочный запрос',1);

При вызове Dequeue извлекается элемент с наименьшим значением приоритета. Поэтому сначала выводится срочный запрос с приоритетом 1, затем формирование отчёта с приоритетом 2 и только потом создание резервной копии с приоритетом 3, хотя оно было добавлено первым.

Название задачи никак не влияет на порядок: очередь сравнивает только значения приоритетов.

Зачем нужна очередь задач

В работающей системе задачи могут поступать быстрее, чем их удаётся выполнять. Например, сервис получает запросы пользователей и одновременно готовит отчёты и резервные копии. Если обрабатывать всё в порядке поступления, срочный запрос будет ждать за менее важными задачами.

Очередь с приоритетами позволяет выбрать самую срочную из ожидающих задач, когда исполнитель освобождается. Новая срочная задача может быть добавлена позже остальных, но извлечена раньше них. Это полезно, например, при распределении обращений в службу поддержки или выборе фоновых заданий для обработки.

При этом PriorityQueue сама не выполняет задачи и не прерывает уже начатую работу — она только хранит элементы и определяет, какой из них извлечь следующим. В нашем примере задачи представлены названиями, поэтому программа лишь выводит их в выбранном порядке. В реальной программе после извлечения запускалась бы соответствующая операция.

Если срочные задачи поступают постоянно, менее важные могут долго оставаться в очереди. Поэтому в реальных системах иногда дополнительно учитывают время ожидания, а не только исходную срочность.

Основные операции PriorityQueue

Enqueue(element, priority) добавляет элемент с заданным приоритетом;
Dequeue удаляет и возвращает элемент с наименьшим приоритетом;
Peek возвращает следующий элемент, не удаляя его;
Count содержит текущее количество элементов;
TryDequeue позволяет безопасно попытаться извлечь элемент и его приоритет.

Если несколько элементов имеют одинаковый приоритет, PriorityQueue не гарантирует для них порядок «первым добавлен — первым извлечён». Если такой порядок важен, его следует задать дополнительно, например включив номер добавления в значение приоритета.

Где применяется очередь с приоритетами

Очереди с приоритетами используются:

при поиске кратчайших путей в графах, например в алгоритме Дейкстры;
при планировании задач;
в моделировании событий;
при обработке запросов разной важности;
во многих других алгоритмах, где каждый следующий элемент выбирается по приоритету.

Классический пример — алгоритм Дейкстры. В статье «Алгоритм Дейкстры в PascalABC.NET» разобрана полная программа поиска кратчайших расстояний в графе с помощью PriorityQueue.

PriorityQueue — ещё один пример того, как PascalABC.NET получает прямой доступ к возможностям стандартной библиотеки .NET 10.