Фундаментальные алгоритмы и структуры данных в Delphi, Бакнелл Джулиан М.

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

на обложку

Бакнелл Джулиан М.

Шрифт:

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

которые необходимо выполнить, и требуется извлечь задачу, обладающую наивысшим приоритетом.

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

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

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

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

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

Первая простая реализация

При разработке очереди по приоритету первый атрибут (возможность хранения произвольного количества элементов) наталкивает на мысль об использовании какой-либо расширяемой структуры данных типа связного списка или расширяемого массива, такого как TList. Мы будем использовать (по крайней мере, пока) TList.

атрибут (возможность добавления элемента в очередь) легко реализовать в случае применения TList: достаточно вызвать метод Add структуры TList. Мы будем исходить из предположения, что добавляемыми в очередь по приоритету элементами будут каким-то образом описанные объекты, свойством которых является их приоритет. В результате мы получаем Достаточно простой элемент, не отвлекающий наше внимание от функциональных возможностей очереди по приоритету.

Реализация третьего атрибута (возможности отыскания наивысшего приоритета и возвращения связанного с ним объекта с удалением его из обрабатываемой очереди по приоритету) несколько сложнее, но все же сравнительно проста. По существу мы выполняем итерационный просмотр элементов структуры TList, сравнивая приоритет каждого элемента с наибольшим обнаруженным приоритетом. Если приоритет данного элемента больше наибольшего обнаруженного до этого момента приоритета, мы помечаем индекс этого элемента как нового элемента с наибольшим приоритетом и переходим к следующему элементу. Этот поиск является простым последовательным поиском. После проверки всех элементов в структуре TList мы знаем, какой их них является наибольшим (его индекс был запомнен), и просто удаляем его из TList.

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

Листинг 9.1. Простая очередь по приоритету, построенная на основе структуры TList type

TtdSimplePriQueuel = class private

FCompare : TtdCompareFunc;

FList : TList;

protected

function pqGetCount : integer;

public

constructor Create(aCompare : TtdCompareFunc);

destructor Destroy; override;

function Dequeue : pointer;

procedure Enqueue(aItem : pointer);

property Count : integer read pqGetCount;