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

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

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

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

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

Для изменения приоритета произвольного элемента следует просто внести изменение, в результате чего элемент может также нарушить свойство пирамидальности.

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

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

Однако вместо этого мы создадим так называемое косвенное сортирующее дерево (indirect heap). При добавлении элемента в очередь по приоритету, управление этим элементом передается очереди. Взамен мы получаем дескриптор (handle). Дескриптор - это значение, по которому очередь "узнает" о добавлении элемента. Если хотите, дескриптор является косвенной ссылкой на реальный элемент в сортирующем дереве.

Итак, чтобы удалить элемент из очереди по приоритету, мы передаем очереди дескриптор этого элемента. Очередь использует этот дескриптор для выяснения позиции элемента в сортирующем дереве, а затем удаляет его, как было описано ранее.

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

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

С точки зрения пользователя очереди по приоритету новый интерфейс лишь немногим сложнее рассмотренного ранее. Код интерфейса класса расширенной очереди по приоритету TtdPriorityQueueEx приведен в листинге 9.9.

Листинг 9.9. Интерфейс класса TtdPriorityQueueEx

type

TtdPQHandle = pointer;

TtdPriorityQueueEx = class private

FCompare : TtdCompareFunc;

FHandles : pointer;

FList : TList;

FName : TtdNameString;

protected

function pqGetCount : integer;

procedure pqError(aErrorCode : integer;

const aMethodName : TtdNameString);

procedure pqBubbleUp(aHandle : TtdPQHandle);

procedure pqTrickleDown(aHandle : TtdPQHandle);

public

constructor Create(aCompare : TtdCompareFunc);

destructor Destroy; override;

procedure ChangePriority(aHandle : TtdPQHandle);

procedure Clear;

function Dequeue : pointer;

function Enqueue(alt em : pointer): TtdPQHandle;

function Examine : pointer;

function IsEmpty : boolean;

function Remove(aHandle : TtdPQHandle): pointer;

property Count : integer read pqGetCount;

property Name : TtdNameString read FName write FName;

end;

Как видите, единственное реальное различие между этим классом и классом TtdPriorityQueue состоит в наличии методов Remove и ChangePriority и в том, что метод Enqueue возвращает дескриптор.

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

Поэтому мы сделаем следующее: когда пользователь будет ставить элемент в очередь, мы будем добавлять элемент в связный список. Это будет сопряжено с определением и использованием узла и, по меньшей мере, двух указателей: указателя самого этого элемента и указателя следующего элемента, хотя по причинам, которые станут понятны несколько позже, мы будем использовать двухсвязный список и поэтому нам потребуется также и предыдущий указатель. Передаваемый нами обратно дескриптор элемента будет адресом узла. Теперь наступает важный момент. Узел хранит также целочисленное значение - позицию элемента в массиве, посредством которого реализовано сортирующее дерево. Сортирующее дерево не хранит сами элементы, а только их дескрипторы (т.е. узлы связного списка). Каждый раз, когда для выполнения сравнения ему нужно будет обратиться к самому элементу, оно будет разыменовывать дескриптор.