Книга: Фундаментальные алгоритмы и структуры данных в Delphi

Очередь по приоритету

Очередь по приоритету

Фактически, упомянутый пример обусловливает название новой структуры данных, называемой очередью по приоритету. Для очереди по приоритету (priority queue) определены две базовых операции: добавление элемента (как и ранее) и извлечение элемента с наивысшим приоритетом. (Естественно, при этом предполагается, что с каждым элементом связано значение приоритета, которое легко проверить.) у читателей может возникнуть вопрос, что в данном контексте понимается под "приоритетом"? Что ж, приоритетом может быть все что угодно. В классическом понимании это численное значение, указывающее на приоритет элемента в каком-либо процессе. Примерами могут служить очереди на печать в операционных системах, очереди заданий или потоки в многопоточной среде. Если принять в качестве примера очередь печати, каждому заданию печати присваивается приоритет - значение, указывающее важность данного задания печати. Задания на печать с высоким приоритетом должны обрабатываться раньше заданий с низким приоритетом. В этом случае операционная система должна была бы завершить выполнение конкретного задания печати, обратиться к очереди печати и извлечь задание печати с наивысшим приоритетом. По мере выполнения работы в операционной системе, другие задания печати будут добавляться в очередь печати с различными приоритетами, а очередь печати обеспечит такую их организацию, чтобы при необходимости можно было определить печатное задание с наивысшим приоритетом.

Однако следует отметить, что используемое в качестве "приоритета" значение не обязательно должно быть классическим номером приоритета. Оно может иметь любой тип или значение - главное, чтобы значения были связаны отношением упорядочения, и чтобы очередь могла определить элемент с наибольшим значением. {Отношение упорядочения набора объектов - это правило, которое позволяет упорядочить объекты так, чтобы объект X был "меньше" объекта Y. Если X меньше Y, то Y не может быть меньше х. Кроме того, если X меньше Y, и Y меньше Z, то X меньше Z. Обычное упорядочение целых чисел, когда 2 меньше 3 и т.д., представляет собой пример отношения упорядочения.}

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

Итак, очередь по приоритету должна обеспечивать (1) хранение произвольного количества элементов, (2) добавление в очередь элемента с определенным приоритетом и (3) выявление и удаление элемента с наивысшим приоритетом.

Оглавление книги