В реальных задачах иногда возникает необходимость в форми-
ровании очередей, отличных от FIFO или LIFO. Порядок выборки
элементов из таких очередей определяется приоритетами элементов.
Приоритет в общем случае может быть представлен числовым значени-
ем, которое вычисляется либо на основании значений каких-либо по-
лей элемента, либо на основании внешних факторов. Так, и FIFO, и
LIFO-очереди могут трактоваться как приоритетные очереди, в кото-
рых приоритет элемента зависит от времени его включения в оче-
редь. При выборке элемента всякий раз выбирается элемент с наи-
большим приоритетом.
Очереди с приоритетами могут быть реализованы на линейных
списковых структурах - в смежном или связном представлении. Воз-
можны очереди с приоритетным включением - в которых последова-
тельность элементов очереди все время поддерживается упорядочен-
ной, т.е. каждый новый элемент включается на то место в
последовательности, которое определяется его приоритетом, а при
исключении всегда выбирается элемент из начала. Возможны и очере-
ди с приоритетным исключением - новый элемент включается всегда в
конец очереди, а при исключении в очереди ищется (этот поиск мо-
жет быть только линейным) элемент с максимальным приоритетом и
после выборки удаляется из последовательности. И в том, и в дру-
гом варианте требуется поиск, а если очередь размещается в стати-
ческой памяти - еще и перемещение элементов.
Наиболее удобной формой для организации больших очередей с
приоритетами является сортировка элементов по убыванию приорите-
тов частично упорядоченным деревом, рассмотренная нами в п.3.9.2.