Каждый элемент в очереди с приоритетом (priority queue) имеет определен-
ный приоритет. Когда программа должна удалить элемент из очереди, она выби-
рает элемент с самым высоким приоритетом. При этом не имеет значения, в каком
порядке элементы хранятся в очереди, так как программа всегда может найти эле-
мент с самым высоким приоритетом.
Некоторые операционные системы используют очереди с приоритетом для
планирования задания. В операционной системе UNIX все процессы имеют раз-
ные приоритеты. Когда процессор освобождается, выбирается готовый к исполне-
нию процесс с максимальным приоритетом. Процессы с меньшим приоритетом
должны ждать завершения или блокировки (например, внешнего события, такого
как чтение данных с диска) процессов с более высокими приоритетами.
Концепция очередей с приоритетами также используется при управлении
авиаперевозками. Самолеты, идущие на посадку из-за отсутствия топлива, име-
ют высший приоритет. Второй приоритет присваивается самолетам, заходящим
на посадку. Самолеты на земле имеют третий приоритет, потому что они нахо-
дятся в более безопасном положении, чем самолеты в воздухе. Через какое-то вре-
мя некоторые приоритеты могут измениться, так как у самолетов, которые пыта-
ются приземлиться, может кончится топливо.
Простой способ организации очереди с приоритетами - поместить всё элемен-
ты в список. Если требуется удалить элемент из очереди, надо найти в списке эле-
мент с наивысшем приоритетом. При использовании этого метода новый элемент
добавляется в очередь всего за один шаг. Чтобы добавить элемент к очереди, вы
размещаете новый элемент в начале списка. Если очередь содержит N элементов,
требуется O(N) шагов, чтобы определить положение и удалить из очереди элемент
с максимальным приоритетом.
Немного удобнее использовать связанный список и хранить элементы, распо-
лагая их в порядке уменьшения приоритета. Тип данных списка TPriorityCell
можно определить следующим образом:
type
String10 = String[10];
PPriorityQCell = ^TPriorityQCell;
TPriorityQCell = record
Value : StringlO;
Priority : Longint;
NextCell : PPriorityQCell;
end;
Чтобы добавить элемент в очередь, необходимо найти для него правильную по-
зицию в списке и поместить его туда. Упростить поиск положения элемента можно
с помощью меток в начале и конце списка, присвоив им соответствующие приори-
теты. Например, если элементы имеют приоритеты от 0 до 100, можно присвоить
метке начала приоритет 101, а метке конца - приоритет -1. Любые приоритеты
реальных элементов будут находиться между этими значениями.
На рис. 3.8 показана очередь с приоритетами, реализованная с помощью свя-
занного списка. Рис. 3.8. Очередь с приоритетами на основе связанного списка
В следующем фрагменте кода приведена основа подпрограммы поиска:
var
new_cell, cell_ptr, next_cell : PPriorityQCell;
begin
// Определение места для нового элемента.
Cell_ptr := @TopSentinel;
next_cell := cell_ptr^.NextCell;
while (next_cell^.Priority>new_priority) do
begin
cell_ptr := next_cell;
next_cell := cell_ptr^.NextCell;
end;
// Вставка новой ячейки.
cell_ptr^.NextCell := new_cell;
new_cell^.NextCell := next_cell;
Чтобы удалить из списка .элемент с самым высоким приоритетом, достаточно
удалить элемент после метки начала. Поскольку список отсортирован в порядке
уменьшения приоритета, первый элемент всегда имеет наивысший приоритет.
Добавление нового элемента в эту очередь в среднем занимает N/2 шагов. Иног-
да новый элемент оказывается в начале списка, а иногда ближе к концу, но в сред-
нем он будет попадать приблизительно в середину. Предыдущая простая очередь
с приоритетом на основе списка требовала О( 1) шагов для добавления нового эле-
мента в очередь и O(N) шагов для удаления элемента с максимальным приорите-
том. В версии на основе сортированного связанного списка элемент добавляется
за O(N) шагов и за О(1) удаляется верхний элемент. Обеим версиям требуется
O(N) шагов для одной из этих операций, но в случае упорядоченного связанного
списка обычно приходится выполнять только N/2 шагов.
Программа PriorQ использует сортируемый связанный список для обработки
очереди с приоритетом. Вы можете задать приоритет и значение элемента данных
и с помощью кнопки Enter добавить его в очередь. Для удаления из очереди эле-
мента с наивысшим приоритетом щелкните по кнопке Leave.
Немного доработав этот пример, можно сформировать очередь с приоритетом,
где добавление и удаление элементов будут занимать O(logN) шагов. Для очень
больших очередей ускорение работы окупит затраченные усилия. Этот тип очере-
дей с приоритетом использует структуры данных в виде пирамиды, которые так-
же применяются в алгоритмах с древовидной сортировкой.
Главная
Каталог файлов
